My iterative solution in java


  • 0
    F

    public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> rets = new ArrayList<Integer>();
    if(root == null) {
    return rets;
    }

        TreeNode t = root;
        TreeNode[] s = new TreeNode[100];   //stack to store the root 
        int[] n = new int[100];             //stack to store the direction to return to root, 0--denotes it return from left subtree, 1 -- denotes that it returns from right substree
        int sn = 0, nn = 0;
        while(t != null || !(sn == 0)) {
            if(t != null) {
                s[sn++] = t; 
                n[nn++] = 0;
                t = t.left;
            }
            else {
                if(n[nn-1] == 0) {
                    t = s[sn - 1];
                    t = t.right;
                    n[nn-1] = 1;                    
                }
                else {
                    t = s[--sn];
                    --nn;
                    rets.add(t.val);
                    t = null;
                }
            }
        }
        return rets;
    }
    

    }


Log in to reply
 

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