A real post order method in Java


  • 0
    M

    I have seen a simple method as modification of preorder to achieve the same result as postorder which is brilliant.

    But the problem is in the real interview the interviewer may want to see if you can code in real post order and doesn't allow you to use this one.

    So below is my postorder method and I think it's pretty simple:

    1, push all the left children in the stack
    2, for the current node:
    2.1: it has no right child or it's right child was visited in the previous traversal, we should add it to result and pop it, set it as the previous visited node
    2.2 : it has right child and it was not visited yet, set the it as current node repeat step 1.

    public class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> rs = new ArrayList<>();
            Stack<TreeNode> st = new Stack<>();
            TreeNode pre = null;
            while (root != null || st.size() > 0) {
                while (root != null) {
                    st.push(root);
                    root = root.left;
                }
                TreeNode cur = st.peek();
                if (cur.right == null || cur.right == pre) {
                    rs.add(cur.val);
                    st.pop();
                    pre = cur;
                } else {
                    root = cur.right;
                }
            }
            return rs;
        }
    }
    

Log in to reply
 

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