构造二叉树

àì夳堔傛蜴生んèń 2023-10-10 15:09 7阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：敲代码の流川枫
> 
> 博客主页：[流川枫的博客][Link 1]
> 
> 专栏：[和我一起学java][java]
> 
> 语录：Stay hungry stay foolish
> 
> 工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
> 
> [点击注册和我一起刷题][Link 2]

## 从前序与中序遍历序列构造二叉树 ##

> 给定两个整数数组 `preorder` 和 `inorder` ，其中 `preorder` 是二叉树的**先序遍历**， `inorder` 是同一棵树的**中序遍历**，请构造二叉树并返回其根节点。
> 
> ![0c48351e2dae4331a783049b45942e30.png][]
> 
> ![7124a1897fc24f679d806189a88405ab.png][]

思路

先序遍历的顺序是根节点，左子树，右子树。中序遍历的顺序是左子树，根节点，右子树。

所以我们只需要根据先序遍历得到根节点，然后在中序遍历中找到根节点的位置，它的左边就是左子树的节点，右边就是右子树的节点。

生成左子树和右子树就可以递归的进行了。

代码

/**
     * 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 int preIndex = 0;
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return buildTreeChild(preorder,inorder,0,inorder.length-1);
        }
        private TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend){
            //当前根节点是否有左右子树
            if(inbegin>inend){
                return null;
            }
            //根节点
            TreeNode root = new TreeNode(preorder[preIndex]);
            //root下标
           int rootIndex = findIndex(inorder,inbegin,inend,preorder[preIndex]);
           preIndex++;
            //左树
            if(rootIndex == -1){
                return null;
            }
            //建左右子树
            root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
            root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
            return root;
        }
        //找到根节点在中序遍历中的下标
         private int findIndex(int[] inorder,int inbegin,int inend,int val){
                for(int i = inbegin;i<=inend;i++)
                {
                    if(inorder[i]==val){
                        return i;
                    }
                }
                return -1;
            }
    }

[ced485cbb11e458d81a746890b32cf3f.gif]: https://img-blog.csdnimg.cn/ced485cbb11e458d81a746890b32cf3f.gif
[Link 1]: https://blog.csdn.net/chenchenchencl?spm=1011.2421.3001.5343
[java]: https://blog.csdn.net/chenchenchencl/category_11932758.html
[Link 2]: https://www.nowcoder.com/link/pc_csdncpt_qdmdlcf_c
[0c48351e2dae4331a783049b45942e30.png]: https://img-blog.csdnimg.cn/0c48351e2dae4331a783049b45942e30.png
[7124a1897fc24f679d806189a88405ab.png]: https://img-blog.csdnimg.cn/7124a1897fc24f679d806189a88405ab.png