剑指 offer 笔记 04 | 重建二叉树

题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

代码

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
       
   }

分析
根据题目要求可知，传入两个数组，一个是前序遍历序列，一个是中序遍历序列。
二叉树的特性，前序规律：中左右，即第一个元素就是「根节点」；中序规律：左中右，「根节点」在中间，根节点左边的是左子树，根节点右边的是右节点。

1）用前序获取到「根节点」；

2）用「根节点」的值，去扫描中序序列，找出中序根节点的位置（索引值）；

3）在中序找到根节点的位置，那么根节点的左边就是左子树，根节点右边的就是右子树；

4）分别找到了左、右子树的前序遍历序列和中序遍历序列，重复步骤1）2）3），本质就是一个递归过程。

代码

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */


/*
*@pre 前序遍历数组
*@preStart 前序数组起始位
*@preEnd 前序数组终止位
*@in 中序遍历数组
*@instart 中序遍历数组起始位
*@inEnd 中序遍历数组终止位
*/
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        TreeNode tree = reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
        return tree;
    }
    //前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
    private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {
         
        if(startPre > endPre||startIn > endIn){
            return null;
        }
        //前序遍历数组的第一个元素就是子树的根节点
        int root = pre[startPre];
        TreeNode tree = new TreeNode(root);
          //根据【前序遍历数组得到的根节点】在【中序遍历数组】中找到根节点所在的位置
        int rootIndex = 0;
         for(int i=startIn;i<=endIn;i++){
            if(in[i] == root){
                rootIndex = i;
                //当前根节点，左子树的节点数/右子树的节点数
                int leftCount = rootIndex - startIn;
                int rightCount = endIn - rootIndex;
                //左右子树递归
                tree.left = reConstructBinaryTree(pre, startPre+1, startPre+leftCount, in, startIn, rootIndex-1);
                tree.right = reConstructBinaryTree(pre, leftCount+startPre+1, endPre, in, rootIndex+1, endIn);
                break;
            }
        }      
        return tree;
    }
}

参考文献：
https://blog.csdn.net/lhl1124281072/article/details/79842315
https://www.nowcoder.com/questionTerminal/8a19cbe657394eeaac2f6ea9b0f6fcf6