leetcode笔记——106从中序后序遍历构造二叉树

小编 2026-07-03 阅读:1907 评论:0

题目：根据一棵树的中序遍历与后序遍历构造二叉树。注意: 你可以假设树中没有重复的元素。例如，给出中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder =...

题目：

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

注意:
你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

思路：在网上找的大神的代码。原文链接：https://blog.csdn.net/wu2304211/article/details/54709205。

与之前105题的思路相同。只不过对于后序遍历最后一个节点是根节点，在中序遍历中找到对应的节点，之前的是左子树，之后的是右子树节点。进行递归知道叶子节点。

代码：

public class Solution { /**
     *@param inorder : A list of integers that inorder traversal of a tree
     *@param postorder : A list of integers that postorder traversal of a tree
     *@return : Root of a tree
     */ //在中序遍历序列中找到根结点的位置
    private int findPosition(int[] array, int start, int end, int key) {
        for (int i = start; i <= end; i++) {
            if (array[i] == key) {
                return i;
            }
        }
        return -1;
    }
    //重建二叉树，通过递归调用来一步步的重建
    private TreeNode myBuildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        if (inStart > inEnd) {
            return null;
        }
        //根据后序遍历序列的最后一个数字建立根结点
         TreeNode root = new TreeNode(postorder[postEnd]);
        //获取根结点的位置
       int position = findPosition(inorder, inStart, inEnd, postorder[postEnd]);
        //创建左子树
        root.left = myBuildTree(inorder, inStart, position - 1, postorder, postStart, postStart + (position - inStart- 1));
        //创建右子树
        root.right = myBuildTree(inorder, position + 1, inEnd, postorder, postStart + (position - inStart), postEnd - 1);
        return root;
        //返回根结点
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // write your code here
        if (inorder.length != postorder.length) {
            return null;
        }
        return myBuildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }
}

执行最快的代码：

两者的思路是相同的，只不过在以下代码中中序遍历也是从后往前，一些代码的形式不同。

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        
        if(inorder.length==0) return null;
        
        return func(postorder,inorder,0,postorder.length-1,0,inorder.length-1);
        
    }
    
    public TreeNode func(int []postorder,int [] inorder,int begin1,int end1,int begin2,int end2)
    {
        if(end1==-1) return null;
        
        TreeNode root =new TreeNode(postorder[end1]);
        
        for(int index=end2;index>=begin2;index--)
        {
            if(postorder[end1]==inorder[index])
            {
                int length=end2-index;
                root.left=func(postorder,inorder,begin1,end1-length-1,begin2,index-1);
                root.right=func(postorder,inorder,end1-length,end1-1,index+1,end2);
                return root;
                
                
            }
            
            
        }
        
        return null;
        
    }
}