三种基本的Tree Traversal

• inorder traversal: left subtree -> root -> right subtree
• preorder traversal: root -> left subtree -> right subtree
• postorder traversal: left subtree -> rightsubtree -> root

常见follow up

• Recursive solution is trivial, could you do it iteratively?
• Could you get a solution with O(1) extra space?
  参考 Morris Traversal方法遍历二叉树，非递归，不用栈，O(1)空间
  

94. Binary Tree Inorder Traversal

//recursive
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }
    private void inorder(TreeNode root, List<Integer> res) {
        if (root == null) return;
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }
}

//iterative
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.empty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode cur = stack.pop();
            res.add(cur.val);
            root = cur.right;
        }
        return res;
    }
}

Morris

• for the cur node, if it does not has left-child, print it, update its right-child as cur
• if cur node has left-child, find the right-most node as pre (the last one that we visit in left-subtree)
  (a) pre's right-child is NULL, pre's right-child points to cur node
  (b) pre's right-child is not NULL, set it to NULL (restore the original tree), print cur, and update cur's right-child as cur

//Morris
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left == null) {
                res.add(cur.val);
                cur = cur.right;
            } else {
                //find the predecesoor of current node
                TreeNode pre = cur.left;
                while (pre.right != null && pre.right != cur) {
                    pre = pre.right;
                }
                if (pre.right != null) {
                    res.add(cur.val);
                    pre.right = null;  //restore the original tree structure
                    cur = cur.right;
                } else {               
                    pre.right = cur;   //predecessor connect to cur
                    cur = cur.left;    //visit next node
                }
            }
        }
        return res;
    }
}

144. Binary Tree Preorder Traversal

//recursive
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        preorder(root, res);
        return res;
    }
    private void preorder(TreeNode root, List<Integer> res) {
        if (root == null) return;
        res.add(root.val);
        preorder(root.left, res);
        preorder(root.right, res);
    }
}

//iterative
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.empty() || root != null) {
            while (root != null) {
                res.add(root.val);
                stack.push(root);
                root = root.left;
            }
            TreeNode cur = stack.pop();
            root = cur.right;
        }
        return res;
    }
}

• 与中序遍历的Morris一样，唯一需要注意的是什么时候打印
• 应该在pre.right == null 中打印，因为这代表了这是我们第一次visit cur
• 需要注意的是，在找predecessor时的条件 (pre.right != null && pre.right != cur)， 缺少后半部分会形成环

//Morris
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left == null) {
                res.add(cur.val);
                cur = cur.right;
            } else {
                TreeNode pre = cur.left;
                while (pre.right != null && pre.right != cur) {
                    pre = pre.right;
                }
                if (pre.right == null) {     //如果右孩子为空，说明是第一次visit这个节点，print
                    res.add(cur.val);
                    pre.right = cur;
                    cur = cur.left;
                } else {
                    //恢复的时候已经打印完了，不应该在这里打印
                    pre.right = null;
                    cur = cur.right;
                }
            }
        }
        return res;
    }
}

145. Binary Tree Postorder Traversal

//recursive
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }
    private void postorder(TreeNode root, List<Integer> res) {
        if (root == null) return;
        postorder(root.left, res);
        postorder(root.right, res);
        res.add(root.val);
    }
}

//iterative
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList res = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.empty() || root != null) {
            while (root != null) {
                res.addFirst(root.val);
                stack.push(root);
                root = root.right;
            }
            TreeNode cur = stack.pop();
            root = cur.left;
        }
        return res;
    }
}

• 后序的Morris就是把前序倒过来，然后插入数的时候插在前面

//Morris
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList res = new LinkedList<>();
        TreeNode cur = root;
        while (cur != null) {
            if (cur.right == null) {
                res.addFirst(cur.val);
                cur = cur.left;
            } else {
                //find predecessor
                TreeNode pre = cur.right;
                while (pre.left != null && pre.left != cur) {
                    pre = pre.left;
                }
                if (pre.left == null) {
                    res.addFirst(cur.val);
                    pre.left = cur;
                    cur = cur.right;
                } else {
                    pre.left = null;
                    cur = cur.left;
                }
            }
        }
        return res;
    }
}