根据一棵树的中序遍历与后序遍历构造二叉树。

偏执的太偏执、 2023-01-12 01:54 109阅读 0赞

## 题目要求 ##

根据一棵树的中序遍历与后序遍历构造二叉树。  
注意: 你可以假设树中没有重复的元素。

例如，给出

//中序遍历 inorder = [9,3,15,20,7]
    //后序遍历 postorder = [9,15,7,20,3]
    //返回如下的二叉树：
    
    //    3
    //   / \
    //  9  20
    //    /  \
    //   15   7

## 代码 ##

private int index2;
        public TreeNode buildTree(int[] preorder, int[] postorder) {
        
            index2 = 0;
            //先逆置
            int length = postorder.length;
            for (int i = 0; i < length / 2; i++) {
        
                int temp = postorder[i];
                postorder[i] = postorder[length - 1 - i];
                postorder[length - 1 - i] = temp;
            }
            return buildTreeHelper(preorder,postorder,0,postorder.length);
        }
    
        private TreeNode buildTreeHelper(int[] preorder, int[] postorder, int left, int right) {
        
            if (left >= right){
        
                //中序遍历结果为空，这个数就是空树
                return null;
            }
            if (index2 >= preorder.length){
        
                return null;
            }
            TreeNode root = new TreeNode((char) preorder[index2]);
            index2++;
            int pos = find(postorder,left,right,root.val);
            root.right = buildTreeHelper(preorder,postorder,pos+1,right);
            root.left = buildTreeHelper(preorder,postorder,left,pos);
    
            //一个树的先序遍历的镜像和后序遍历的逆置相同，，，，根右左
            //所以先逆置后序遍历，再调整左右根的打印位置
    
            return root;
        }
    
        private int find(int[] inorder, int left, int right, int toFind) {
        
            for (int i = left; i < right; i++){
        
                if (inorder[i] == toFind){
        
                    return i;
                }
            }
            return -1;
        }