[java/1ms] explain for pre, in, postorder in brief words, code yourself.


  • 0

    The difficult part of this three is when to print parent node. And here I will explain in brief.

    null is special, and considered as a child since you will check whether the child is null or not. If it's null child, and it can be treated as return from that null child when you draw a graph.

    In this logic, leaf node should be viewed as parent of 2 null children. And you should draw a leaf node in this manner:

    leaf node ---> null
    |
    \ __>null

    So draw a picture by yourself to trace the path of the traversal with following rule:

    1. Preorder: print parent directly.
    2. Inorder: print parent when return from left child.
    3. Postorder: print parent when return from right child.
    public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            if (root == null) return res;
    
            Stack<TreeNode> stack = new Stack<>();
            stack.add(root);
    
            while (!stack.isEmpty()) {
                TreeNode node = stack.peek();
                if (node.right != null)
                    stack.add(node.right);
    
                if (node.left != null)
                    stack.add(node.left);
    
                if (node.left == null && node.right == null) {
                    node = stack.pop();
                    res.add(node.val);
                    while (!stack.isEmpty() && // isParent?
                            (stack.peek().right == node || stack.peek().left == node)) {
                        // right child can be null, if stack.peek().left == node, then return from it.
                        node = stack.pop();
                        res.add(node.val);
                    }
                }
            }
    
            return res;
        }
    

Log in to reply
 

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