剑指Offer #04 重建二叉树（递归）

妖狐艹你老母 2023-07-07 12:59 2阅读 0赞

> 题目来源：牛客网-剑指Offer专题  
> 题目地址：[重建二叉树][Link 1]

### 题目描述 ###

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

### 题目解析 ###

第  n + 1 n+1 n\+1 次遇到这种题目了，简单写一下思路吧。

*  根据前序遍历的性质确定根节点，然后在中序遍历中查询根节点的位置。
 *  这样就得到了中序遍历左右子树的范围了，接下来就是要求左子树的节点的个数。
 *  求得左子树节点个数之后，我们就知道了前序遍历中左右子树的范围了。
 *  建树的过程是**递归**的，我们要做的就是**对左右子树重复上述过程**。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ_size_16_color_FFFFFF_t_70]  
    （上图为一次求解过程的图示）

想看更详细解析的可以看这篇：[L2-006 树的遍历-团体程序设计天梯赛GPLT][L2-006 _-_GPLT]

/** * 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) { 
            int r = pre.length - 1;
            TreeNode root = buildTree(pre, in, 0, r, 0, r);
            return root;
        }
        //[la,ra]为前序遍历序列范围，[lb,rb]为中序遍历序列的范围
        public TreeNode buildTree(int [] pre,int [] in,
                                  int la, int ra, int lb, int rb) { 
            if (la > ra || lb > rb) { 
                return null;
            }
            //num表示根节点的权值
            int num = pre[la];
            TreeNode rt = new TreeNode(num);
            //p表示根节点在中序遍历序列中的位置
            int p = lb;
            while (p <= rb && in[p] != num) p++;
            //cnt表示左子树节点的个数
            int cnt = p - lb;
            //递归建树
            rt.left = buildTree(pre, in, la + 1, la + cnt, lb, p - 1);
            rt.right = buildTree(pre, in, la+ cnt + 1, ra, p + 1, rb);
            return rt;
        }
    }

--------------------

如果本文对你有所帮助，要记得点赞哦~

[Link 1]: https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&tqId=11157&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200224135941666.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ==,size_16,color_FFFFFF,t_70
[L2-006 _-_GPLT]: https://blog.csdn.net/weixin_42292229/article/details/104471619