ChunNote
0%

leetCode-106:Construct Binary Tree from Inorder and Postorder Traversal

发表于 分类于

问题描述

给定一个二叉树的中序遍历数组和后序遍历数组，要求构造这颗树并返回根节点。题目链接：**点我**

样例输入输出

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]

输出：[3,9,20,null,null,15,7]

解释：树的形状如下

tree

输入：inorder = [-1], postorder = [-1]

输出：[-1]

问题解法

此题没有什么特殊的算法，就是按照中序遍历和后序遍历对数组进行拆分，依次构造子树，最后连接成最终结果。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }

    private TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }
        
        int rootValue = postorder[postEnd];
        if (postStart == postEnd) {
            return new TreeNode(rootValue);
        }

        int i;
        for (i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootValue) {
                break;
            }
        }

        int leftSize = i - inStart;
        TreeNode left = buildTree(inorder, inStart, i - 1, postorder, postStart, postStart + leftSize - 1);
        TreeNode right = buildTree(inorder, i + 1, inEnd, postorder, postStart + leftSize, postEnd - 1);
        return new TreeNode(rootValue, left, right);
    }
}