Binary Tree Traversal

浠ラ箍發(fā)布于2019-08-14 17:17 / 2015人閱讀

PostOrder

public class Solution {
    // Important, when you pop a node, ensure its children are traversed.
    public List postorderTraversal(TreeNode root) {
        ArrayDeque s = new ArrayDeque();
        List ans = new ArrayList();
        TreeNode cur = root;
        
        while (cur != null || !s.isEmpty()) {
            while (cur != null) {
                s.push(cur);
                cur = cur.left;
            }
            
            while (!s.isEmpty() && cur == s.peek().right) {
                cur = s.pop();
                ans.add(cur.val);
            }
            
            if (s.isEmpty()) cur = null; else cur = s.peek().right;
        }
        
        return ans;
    }
    
}

PreOrder

public class Solution {
    public List preorderTraversal(TreeNode root) {
        List res = new LinkedList();
        ArrayDeque stk = new ArrayDeque();
        TreeNode cur = root;
        
        while(cur != null || !stk.isEmpty()){
            if(cur != null) {
                stk.push(cur);
                res.add(cur.val);   // add val before going to children
                cur = cur.left;
            } else {
                TreeNode node = stk.pop();
                cur = node.right;
            }
        }
        return res;
    }
}

InOrder

public class Solution {
    public List inorderTraversal(TreeNode root) {
        List res = new ArrayList();
        if(root == null) return res;
        ArrayDeque stk = new ArrayDeque();
        TreeNode cur = root;
        
        while(cur != null || !stk.isEmpty()){
            if(cur !=null) {
                stk.push(cur);
                cur = cur.left; 
            } else {
                TreeNode node = stk.pop();
                res.add(node.val);        // add after all left children
                node = node.right;
            }
        }
        return res;
    }
}

PreOrder

public class Solution {
    public List preorderTraversal(TreeNode root) {
        List res = new LinkedList();
        ArrayDeque stk = new ArrayDeque();
        if(root == null) return res;
        TreeNode cur = root;
        stk.push(cur);
        
        while(!stk.isEmpty()){
            cur = stk.pop();
            res.add(cur.val);
            if(cur.right != null) stk.push(cur.right);
            if(cur.left != null) stk.push(cur.left);
        }
        return res;
    }
}

InOrder

public class Solution {
    public List inorderTraversal(TreeNode root) {
        List res = new ArrayList();
        if(root == null) return res;
        ArrayDeque stk = new ArrayDeque();
        TreeNode cur = root;
        
        while(cur != null || !stk.isEmpty()){
            while(cur != null) {
                stk.push(cur);
                cur = cur.left;
            }
            cur = stk.pop();
            res.add(cur.val);
            cur = cur.right;
        }
        return res;
    }
}