4____重构二叉树

一时失言乱红尘 2023-08-17 17:21 89阅读 0赞

题目描述：

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{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) {
            TreeNode root=rebuilder(0,pre.length-1,0,in.length-1,pre,in);
            return root;
        }
        
        public TreeNode rebuilder(int pS,int pE,int iS,int iE,int[]pre,int[]in){
            if(pS>pE||iS>iE){  //递归结束的条件
                return null;
            }
            TreeNode root=new TreeNode(pre[pS]); //创建根结点
            
            for(int i=0;i<in.length;i++){
                if(in[i]==pre[pS]){  //找到中序遍历中根节点的位置
                    //递归创建左子树  前序遍历中加上中序中子树的长度
                    root.left=rebuilder(pS+1,pS+i-iS,iS,i-1,pre,in);
                    
                    //递归遍历右子树 pS+左子树的长度
                    root.right=rebuilder(pS+i-iS+1,pE,i+1,iE,pre,in);
                    
                    break;
                }
            }
            
            return root;
        }
    }

采用递归的思想：

前序遍历的第一个元素是根节点；

在中序遍历中根节点左边的元素都是左子树；

中序遍历的根节点的右边元素都是右子树。

转载于:https://www.cnblogs.com/xbfchder/p/11446782.html

发表评论取消回复

表情：

评论列表（有 0 条评论，89人围观）

还没有评论，来说两句吧...

相关阅读

相关 4____重构二叉树

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

一时失言乱红尘/ 2023年08月17日 17:21/ 0 赞/ 90 阅读

相关真二叉树重构(Proper Rebuild)

题目真二叉树重构(Proper Rebuild) Description In general, given the preorder traversal seq

Love The Way You Lie/ 2023年02月14日 13:25/ 0 赞/ 1 阅读

相关 C语言重构【226】翻转二叉树

文章目录所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)

超、凢脫俗/ 2022年12月16日 13:26/ 0 赞/ 196 阅读

相关周末说说二叉树之重构

老师在讲这个根据前序，中序的结果重建二叉树的时候，事实上是给出了流程图的，但递归的方法更简单： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW

﹏ヽ暗。殇╰゛Y/ 2022年12月10日 11:29/ 0 赞/ 74 阅读

相关 C语言重构【110】平衡二叉树

文章目录所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)

左手的ㄟ右手/ 2022年12月08日 15:30/ 0 赞/ 170 阅读

相关 ACM 重构二叉树 C++实现

重构二叉树 Description 根据输入的二叉树前序和中序遍历序列重构二叉树，输出对应节点的左右子节点。输入：第一行是一个整数N（1<=N<=20），表示有

阳光穿透心脏的1/2处/ 2022年06月18日 11:11/ 0 赞/ 123 阅读

相关二叉树4--求二叉树的深度

1、题目： Given a binary tree, find its maximum depth. The maximum depth is the number of

绝地灬酷狼/ 2022年05月25日 11:29/ 0 赞/ 240 阅读

相关 ACM 重构二叉树 C++实现

重构二叉树 Description 根据输入的二叉树前序和中序遍历序列重构二叉树，输出对应节点的左右子节点。输入：第一行是一个整数N（1<=N<=20），表示有

朱雀/ 2022年05月15日 13:15/ 0 赞/ 155 阅读

相关 ACM 重构二叉树 C++实现

重构二叉树 Description 根据输入的二叉树前序和中序遍历序列重构二叉树，输出对应节点的左右子节点。输入：第一行是一个整数N（1<=N<=20），表示有

柔情只为你懂/ 2022年05月15日 13:15/ 0 赞/ 188 阅读

相关《剑指offer》之重构二叉树

《剑指offer》之重构二叉树题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列

分手后的思念是犯贱/ 2022年03月19日 05:44/ 0 赞/ 132 阅读