重建二叉树

偏执的太偏执、 2022-03-25 15:18 141阅读 0赞

# [重建二叉树][Link 1] #

## 题目描述 ##

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

1 //二叉树结构体
     2 public class TreeNode {
     3 
     4     int val;
     5     TreeNode left;
     6     TreeNode right;
     7 
     8     public TreeNode(int x) {
     9 
    10         this.val = x;
    11     }
    12 
    13 }

![1456741-20180804094918655-1087288921.png][]

思路：

本题对于前序中序或者后续中序方法是一样的，都是根据中序和另外一个序列的root来确定 i 的值， 然后通过递归确定左右子树

![1456741-20180804103953949-954132208.png][]

1  public class Solution {
     2      public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
     3      TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
     4      return root;
     5          }
     6      //前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
     7      private TreeNode reConstructBinaryTree(int [] pre,int PreL,int PreR,int [] in,int InL,int InR) {
     8 
     9      if(PreL>PreR||InL>InR)
    10      return null;
    11      TreeNode root=new TreeNode(pre[PreL]);
    12 
    13      for(int i=InL;i<=InR;i++)
    14      if(in[i]==pre[PreL]){
    15      int numberLeft=i-InL;
    16      root.left=reConstructBinaryTree(pre,PreL+1,PreL+numberLeft,in,InL,i-1);
    17      root.right=reConstructBinaryTree(pre,PreL+numberLeft+1,PreR,in,i+1,InR);
    18      
    19      //根据后序和中序构建相关二叉树
    20      //root.left=reConstructBinaryTree(post, PostL, PostL+numberLeft-1, in, InL, i-1);
    21      //root.right=reConstructBinaryTree(post, PostL+numberLeft, PostR-1, in, i+1, InR);
    22      break;
    23      }
    24 
    25      return root;
    26          }
    27      }

posted @ 2018-08-04 10:44 [Octopus22][] 阅读( ...) 评论( ...) [编辑][Link 2] 收藏

[Link 1]: https://www.cnblogs.com/Octopus-22/p/9417806.html
[1456741-20180804094918655-1087288921.png]: /images/20220325/c5f173fac5564088b18b51e7bbac4993.png
[1456741-20180804103953949-954132208.png]: /images/20220325/7e2ed3b19e2741c082f992402960b54e.png
[Octopus22]: https://www.cnblogs.com/Octopus-22/
[Link 2]: https://i.cnblogs.com/EditPosts.aspx?postid=9417806