树的遍历

树的三序遍历是基本

递归写法 迭代写法

• preorder 直接用 stack;
• inorder 用 stack + cur;
• postorder 用 stack + cur + prev;

Pre-order

recursive solution is trivial

public class Solution {
    // recursive
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, result);
        return result;
    }

    public void dfs(TreeNode root, List<Integer> result) {
        if(root == null) return;

        result.add(root.val);

        dfs(root.left, result);
        dfs(root.right, result);
    }

    // iteration
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        // error-prone
        if(root != null) stack.push(root);

        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);
            // first right
            if(node.right != null) stack.push(node.right);
            if(node.left != null) stack.push(node.left);
        }

        return result;
    }
}

In-Order

recursive solution is trivial

public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;

        while(!stack.isEmpty() || cur != null ) {
            while(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            TreeNode node = stack.pop();
            result.add(node.val);
            cur = node.right;
        }
        return result;       
    }
}

Construct Binary Tree from Preorder and Inorder Traversal (Snapchat)

要学会用 continuous subarray 的眼光去看三序遍历数组，子树结构 = 子序列结构

In-order 和 pre-order 单独都只能提供一部分树的信息，只依靠一个无法建立出完全一样的树，因为有歧义。

因此根据 inorder 和 preorder 的性质，我们用 preorder 的顺序决定“先建哪个为 root”，用 inorder 的相对位置决定 “左右子树是谁”。

这题是关于preorder的遍历

In-order: 【(2,5,3) 1 (4,7,6)】 Pre-order: 【1 (5,2,3) (4,6,7)】

维护什么变量？ preorderRoot, inorderStart, inorderEnd

通过这三个变量可以定位出左子树，右子树

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder, 0, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int[] inorder, int preorderRoot, int inorderStart, int inorderEnd) {
        if(inorderStart > inorderEnd || preorderRoot >= preorder.length) return null;

        int rootVal = preorder[preorderRoot];
        int pos;
        for(pos = inorderStart; pos <= inorderEnd; pos++ ) {
            if(rootVal == inorder[pos]) break;
        }

        TreeNode root = new TreeNode(rootVal);
        root.left = build(preorder, inorder, preorderRoot + 1, inorderStart, pos - 1);
        root.right = build(preorder, inorder, preorderRoot + pos - inorderStart + 1, pos + 1, inorderEnd);

        return root;
    }
}