剑指 Offer 07. 重建二叉树

左手的ㄟ右手 2022-12-16 11:57 156阅读 0赞

# 题目 #

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

例如，给出

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

返回如下的二叉树：  
![在这里插入图片描述][20201020094243622.png_pic_center]

限制：  
0 <= 节点个数 <= 5000

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof][https_leetcode-cn.com_problems_zhong-jian-er-cha-shu-lcof]

# 解题思路 #

*  前序遍历,根左右,数组的第一个元素是根节点,树的左子树和右子树也是前序遍历
 *  中序遍历,左根右,确定了树的根节点就可以划分左子树和右子树,树的左子树和右子树也是中序遍历

核心思想还是递归,构建当前节点,递归构建当前节点的左子树和右子树

*  前序遍历数组的边界\[preStart,preEnd\]
 *  中序遍历数组的边界\[inStart,inEnd\]
 *  递归结束条件:前序遍历或者中序遍历的边界越界
 *  从前序遍历的数组中获取到根节点,在中序遍历数组中查找到根节点的下标index
 *  递归构建左子树
 *  递归构建右子树
 *  返回当前节点

左子树边界问题:

*  前序遍历边界:
    
     *  左边界:preStart + 1,根节点后面一个
     *  右边界:preStart + index - inStart,左子树的长度=index - inStart(其实就是计算inStart到index - 1之间的长度),右边界也就是计算preStart + 1加上左子树长度后的右边界下标
 *  中序遍历边界:
    
     *  左边界:inStart,中序遍历数组左边界
     *  右边界:index - 1,根节点前面一个

右子树边界问题:

*  前序遍历边界:
    
     *  左边界:preStart + index - inStart + 1,左子树后面一个
     *  右边界:preEnd,前序遍历数组右边界
 *  中序遍历边界:
    
     *  左边界:index + 1,根节点后面一个
     *  右边界:inEnd,中序遍历数组右边界

# 代码 #

/** * 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 == null || inorder == null || preorder.length == 0 || inorder.length == 0) { 
                return null;
            }
            
            return recur(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
        }
    
        private TreeNode recur(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) { 
            // 校验边界是否正确
            if (preStart > preEnd || inStart > inEnd) { 
                return null;
            }
    
            // 创建根节点,先序遍历第一个元素
            int val = preorder[preStart];
            TreeNode node = new TreeNode(val);
    
            // 获取根节点在中序遍历中的位置
            int index = inStart;
            for (int i = inStart; i <= inEnd; i++) { 
                if (val == inorder[i]) { 
                    index = i;
                }
            }
            
            // 左子树
            // 前序遍历左子树边界:[preStart + 1, preStart + index - inStart]
            // 中序遍历左子树边界:[inStart, index - 1]
            node.left = recur(preorder, preStart + 1, preStart + index - inStart, inorder, inStart, index - 1);
            // 右子树
            // 前序遍历右子树边界:[preStart + index - inStart + 1, preEnd]
            // 中序遍历右子树边界:[index + 1, inEnd]
            node.right = recur(preorder, preStart + 1 + index - inStart, preEnd, inorder, index + 1, inEnd);
            return node;
        }
    }

[20201020094243622.png_pic_center]: /images/20221123/0b1263aec84c475c99ce545dd619c893.png
[https_leetcode-cn.com_problems_zhong-jian-er-cha-shu-lcof]: https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof