剑指 Offer 07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

例如,给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树:

    3
   / \
   9  20
     /  \
    15   7
限制:

0 <= 节点个数 <= 5000

注意:本题与主站 105 题重复:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

解决方案

前序遍历序列的第一个数字就是根节点的值,中序遍历序列根节点前面的数是左子树节点的值,反之则是右子树的值。递归做上述动作即可。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || preorder.length != inorder.length) {
            return null;
        }
        int rootVal = preorder[0], rootIndex = -1;
        while (inorder[++rootIndex] != rootVal) { }
        TreeNode root = new TreeNode(rootVal);
        root.left = buildTree(Arrays.copyOfRange(preorder, 1, 1 + rootIndex),
                Arrays.copyOfRange(inorder, 0, rootIndex));
        root.right = buildTree(Arrays.copyOfRange(preorder, 1 + rootIndex, preorder.length),
                Arrays.copyOfRange(inorder, 1 + rootIndex, inorder.length));
        return root;
    }
}
/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun buildTree(preorder: IntArray, inorder: IntArray): TreeNode? {
        if (preorder.isEmpty() || inorder.isEmpty()) {
            return null
        }
        val rootVal = preorder.first()
        var rootIndex = -1
        while (inorder[++rootIndex] != rootVal) { }
        val root = TreeNode(rootVal)
        root.left = buildTree(preorder.copyOfRange(1, 1 + rootIndex), 
                inorder.copyOfRange(0, rootIndex))
        root.right = buildTree(preorder.copyOfRange(1 + rootIndex, preorder.size),
                inorder.copyOfRange(rootIndex + 1, inorder.size))
        return root
    }
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据