Java Stack with explanation


  • 0
    public class Solution {
        /*
        stack里只需要存放TreeNode就好了,流程就是for循环扫String,如果遇到数字,生成TreeNode放入stack中,如果遇到‘(’不管,如果遇到‘)’,就需要从stack中pop出两个TreeNode进行拼接,第一个pop出来的是kid,第二个pop出来的是parent,先判断parent是否有左孩子了,如果有,那么kid就为par的右节点,然后再把par重新放回stack中。依照这个规律跑即可。注意一点是数字的计算,和负号,因为输入里会有“-”表示负数
        */
        public TreeNode str2tree(String s) {
            if (s == null || s.length() == 0) return null;
            Deque<TreeNode> stack = new LinkedList<>();
            boolean positive = true;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == ')') { //pop两次Node出来拼接后放入stack中
                    TreeNode kid = stack.pop();
                    TreeNode par = stack.pop();
                    if (par.left == null) par.left = kid;
                    else par.right = kid;
                    stack.push(par);
                } else if (s.charAt(i) == '-') {
                    positive = false;
                } else if (Character.isDigit(s.charAt(i))) {
                    int num = 0;
                    while (i < s.length() && Character.isDigit(s.charAt(i))) {
                        num = num * 10 + (s.charAt(i++) - '0');
                    }
                    TreeNode node = new TreeNode(positive ? num : -num);
                    stack.push(node);
                    i--;//因为上面计算数字的时候i不断++,最外层for循环又i++了,所以这里需要i--一次
                    positive = true;
                }
            }
            return stack.pop();
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.