Lihang Liu's Homepage > Archive > LeetCode 笔记 3：Construct Binary Tree from xxx Traversal

LeetCode 笔记 3：Construct Binary Tree from xxx Traversal

February 26, 2023

这一类题目（具体题目可以参考文末的链接）要求我们从 inorder, preorder 及 postorder traversal 其中的两个构建出二叉树，之所以能够通过这三种遍历方式中的两个就构建出整棵二叉树，是因为任意两种遍历方式都能够帮助我们递归地找出当前 subroot 的 left 和 right subtree 的范围。而这要从这三种遍历方式的特点说起：

class TreeNode {

    int val;  
    TreeNode left;  
    TreeNode right;  

    TreeNode() {  
    }

    TreeNode(int val) {  
        this.val = val;  
    }

    TreeNode(int val, TreeNode left, TreeNode right) {  
        this.val = val;  
        this.left = left;  
        this.right = right;  
    }

    public static void preorder(TreeNode root, List<Integer> list) {  
        if (root == null) {  
            return;  
        }  
        list.add(root.val);  
        preorder(root.left, list);  
        preorder(root.right, list);  
    }

    public static void postorder(TreeNode root, List<Integer> list) {  
        if (root == null) {  
            return;  
        }  
        postorder(root.left, list);  
        postorder(root.right, list);  
        list.add(root.val);  
    }

    public static void inorder(TreeNode root, List<Integer> list) {  
        if (root == null) {  
            return;  
        }  
        inorder(root.left, list);  
        list.add(root.val);  
        inorder(root.right, list);  
    }
}

	`inorder`	`preorder`	`postorder`
节点遍历顺序	`root.left` -> `root` -> `root.right`	`root` -> `root. left` -> `root.right`	`root.left` -> `root.right` -> `root`
subroot 在 sublist 中的位置（sublist 指遍历 subroot 所在的子树而构成的序列）	无法单独确定	`sublist[0]`	`sublist[sublist.length - 1]`
特性		根据 `preorder` 的特性，`subroot` 在当前子序列中的下一个元素一定是 `subroot.left` （如果还有的话），也就是 `subroot.left = sublist[1]`	根据 `postorder` 的特性，`subroot` 在当前子序列中的前一个元素一定是 `subroot.right` （如果还有的话），也就是 `subroot.right = sublist[sublist.length - 2]`
子序列情况	`[左子树子序列][subroot][右子树子序列]`	`[subroot][左子树子序列][右子树子序列]`	`[左子树子序列][右子树子序列][subroot]`

我们可以总结出，可以很容易从 preorder 以及 postorder 序列中得到 subroot 的值，这是因为 subroot 在这两种递归算法中总是被优先以及最后处理的，所以 subroot 总是出现在子序列的开头或者末尾。

而 inorder 则无法单独判断出 subroot 的位置，但一旦从 preorder 和 postorder 中知道 subroot 的值，那么就可以轻松知道 subroot 的左子树和右子树的范围（在 inorder 序列中，找到 subroot 的 index，位于 index 左边的归属于左子树，右边的归属于右子树）。

而且，一旦我们知道了左子树和右子树的数组长度，我们就可以很轻易地计算出 subroot.left 以及 subroot.right 在 preorder 以及 postorder 数组中的下标了。

因此，我们也就可以递归地从 3 种遍历序列中构建出整棵二叉树。

例题

Example 1: 105. Construct Binary Tree from preorder and inorder Traversal

通过之前的讨论，我们通过 preorder 可以知道 subroot 的位置，那么，在 inorder 数组中找到 subroot 的 index ，位于 index 左边和右边的子序列就对应当前 subroot 的左子树以及右子树，确定左子树和右子树的范围也不再是难事。

算法如下：

rootPreIndex ：当前 subroot 在 inorder 数组的 index
inorderLeft , inorderRight : 当前子树用到的 inorder 数组的左边界和右边界，用于控制递归终止的条件（base case）
找到 subroot 在 inorder 数组中的 index ： rootInorderIndex
计算 subroot.left 子树的长度 leftSubTreeSize = rootInorderIndex - inorderLeft
递归地构造左子树： root.left = build(preorder, inorder, rootPreIndex + 1, inorderLeft, rootInorderIndex - 1); ，其中：
- rootPreIndex + 1 表示 root.left 在 preorder 数组的 index ；
- 左子树在 inorder 数组中的左边界和当前 subroot 是共享的： inorderLeft ；
- 左子树在 inorder 数组中的右边界应该是 subroot 在 inorder 数组中的 index 减去 1： rootInorderIndex - 1 ；
- 也就是 [inorderLeft, rootInorderIndex - 1] 是左子树在 inorder 数组中的范围；
递归地构造右子树： root.right = build(preorder, inorder, rootPreIndex + leftSubTreeSize + 1, rootInorderIndex + 1, inorderRight); ，其中：
- subroot.right 在 preorder 数组中的 index 应该是 rootPreIndex 加上 subroot 的左子树的长度： subrootPreIndex + leftSubTreeSize + 1 ；
- subroot.right 在 inorder 数组中的左边界应该是 rootInorderIndex + 1 ；
- subroot.right 在 inorder 数组中的右边界应该是和当前 subroot 共享的，因此
- [rootInorderIndex + 1, inorderRight] 是右子树在 inorder 数组中的范围

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

    public TreeNode build(int[] preorder, int[] inorder, int rootPreIndex, int inorderLeft, int inorderRight) {
        if (inorderLeft > inorderRight || rootPreIndex < 0 || rootPreIndex >= preorder.length) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[rootPreIndex]);

        int rootInorderIndex = -1;

        for (int i = 0; i < inorder.length; ++i) {
            if (inorder[i] == root.val) {
                rootInorderIndex = i;
                break;
            }
        }

        int leftSubTreeSize = rootInorderIndex - inorderLeft;

        root.left = build(preorder, inorder, rootPreIndex + 1, inorderLeft, rootInorderIndex - 1);
        root.right = build(preorder, inorder, rootPreIndex + leftSubTreeSize + 1, rootInorderIndex + 1, inorderRight);
        
        return root;
    }
}

Example 2: 889. Construct Binary Tree from preorder and postorder Traversal

这道题目和之前的类似，只不过换成了 preorder 和 postorder 的组合，这也导致我们能够利用的信息有了变化：我们不再能通过 inorder 计算出左子树以及右子树的长度了，我们得通过另外的途径来进行计算。

之前也有提到过， preoder 和 postorder 有一个特性，就是：

① 假设 subroot 在 preorder 中的下标是 rootPreIndex ，那么 subroot.left 在 preorder 中的下标一定是 rootPreIndex + 1 ；
② 假设 subroot 在 postorder 中的下标是 rootPostIndex ，那么 subroot.right 在 postorder 的下标一定是 rootPostIndex - 1 ；

我们再结合两种遍历所构成的子序列的情况一起分析：

③ preorder 子序列情况： [subroot][左子树子序列][右子树子序列]
④ postorder 子序列情况： [左子树子序列][右子树子序列][subroot]

那么，我们可以通过结合 ② 和 ③，可以导出：

我们通过 ② 知道了 subroot.right 的值，就可以得到它在 preorder 中的位置，它位于 preorder 数组中 [右子树子序列] 的第一个位置；
既然知道了右子树在 preorder 中的位置，那么左子树的长度就可以通过： rightSubrootPreIndex - subrootPreIndex - 1 得到；
右子树的长度当然也可以通过当前 preorder 的右边界减去 subroot.right 在 preorder 中的 index 得到

同样，我们结合 ① 和 ④，也可以推断得到：

我们通过 ① 知道了 subroot.left 的值，那么就可以知道 subroot.left 在 postorder 数组中的位置，它一定处在 postorder 数组中的 [左子树子序列] 的最后一个位置；
既然知道了左子树序列的首尾位置，那么就可以计算出左子树的长度： leftSubrootPostIndex - postLeft + 1 ；

那么，现在我们获得了递归算法所需的一切条件：

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

    private TreeNode build(int[] pre, int[] post, int preLeft, int preRight, int postLeft, int postRight) {
        if (preLeft > preRight) {
            return null;
        }

        TreeNode root = new TreeNode(pre[preLeft]);

        if (preLeft + 1 > preRight) {
            return root;
        }

        int leftSubRootPostIndex;
        for (leftSubRootPostIndex = postLeft; leftSubRootPostIndex <= postRight; ++leftSubRootPostIndex) {
            if (post[leftSubRootPostIndex] == pre[preLeft + 1]) {
                break;
            }
        }

        int leftSubtreeLength = leftSubRootPostIndex - postLeft + 1;

        root.left = build(pre, post, preLeft + 1, preLeft + leftSubtreeLength, postLeft, postLeft + leftSubtreeLength - 1);

        root.right = build(pre, post, preLeft + leftSubtreeLength + 1, preRight, postLeft + leftSubtreeLength, postRight - 1);
        return root;
    }
}