重建二叉树

ゝ一世哀愁。 2022-05-26 07:57 185阅读 0赞

![这里写图片描述][70]

class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    
     //重建二叉树
    public class Solution {
        public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
    
          if(pre==null||in==null||pre.length==0||in.length==0)
          {
                return null;
          }
          TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
          return root;
        }
        //采用递归的思想重新构建二叉树
        private TreeNode reConstructBinaryTree(int[]pre,int preStart,int PreEnd,int[]in,int inStart,int inEnd)
        {
              if(preStart>PreEnd||inStart>inStart)
                return null;
              TreeNode root=new TreeNode(pre[preStart]); //第一个为根节点
              for(int i=inStart;i<=inEnd;i++)
              {
                       if(in[i]==pre[preStart]){
                          root.left=reConstructBinaryTree(pre,preStart+1,preStart+i-inStart,in,inStart,i-1);
                          root.right=reConstructBinaryTree(pre,i-inStart+preStart+1,PreEnd,in,i+1,inEnd);
                          break;
                       }
              }
              return root;
    
        } 
    
        //二叉树的后序遍历
        public void posTree(TreeNode root)
        {
    
             if(root!=null)
             {
                posTree(root.left);
                posTree(root.right);
                visit(root);
             }
        }
    
    
        public void visit(TreeNode node)
        {
             System.out.print(node.val);
        }
        public static void main(String[]args){
            //System.out.println("Hello");
             int[]pre={
       1,2,4,7,3,5,6,8};
             int[]in={
       4,7,2,1,5,3,8,6};
             Solution s=new Solution();
             s.posTree(s.reConstructBinaryTree(pre,in));
    
        }
    }

![这里写图片描述][70 1]

[70]: /images/20220526/9cab90a1c3f74fc6ac21c02d960a62ad.png
[70 1]: /images/20220526/790a7ec1a3d541f6b0b2f25d1d44c6b4.png