给定二叉树的中序和后序遍历构建二叉树

港控/mmm° 2022-05-19 13:42 193阅读 0赞

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

class TreeNode {
          int val;
         TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
      }
    
    public class Solution {
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            if(inorder==null||inorder.length==0) return null;
    
            return buildBinaryTree(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
        }
        //递归调用重构二叉树
        private TreeNode buildBinaryTree(int[]inorder,int inleft,int inRight,int[]postorder,int postLeft,int postRight){
    
            if(inleft>inRight)
                return null;
            TreeNode root=new TreeNode(postorder[postRight]);
            //只有一个节点，直接返回root
            if(inleft==inRight)
                return root;
            int rootNum=0;
            for(int i=inleft;i<=inRight;i++){
               if(inorder[i]==postorder[postRight]){
                   rootNum=i;
                   break;
               }
            }
            int leftLength=rootNum-inleft;
            //递归调用左子树和右子树
            root.left=buildBinaryTree(inorder,inleft,inleft+leftLength-1,postorder,postLeft,postLeft+leftLength-1);
            root.right=buildBinaryTree(inorder,inleft+leftLength+1,inRight,postorder,postLeft+leftLength,postRight-1);
    
            return root;
        }
    
        public static void main(String[]args){
            System.out.println("Hello World!");
    
        }
    }

[70]: /images/20220519/6619d481b35547bd9c6e7334ede8b3c8.png