东哥带你刷二叉树（构造篇） :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：东哥带你刷二叉树（构造篇）

评论礼仪 见这里，违者直接拉黑。

[DA-MO-WANG]

囊中羞涩的小弟到此一游

[Feyl]

小建议~
求最大值那边可以简化为只记录最大值的数组下标，通过下标可以直接访问到数组最大值，不需要另外使用变量记录最大值。

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return getRoot(nums,0,nums.length-1);
    }
    TreeNode getRoot(int[] nums,int l,int r){
        if(l>r) return null;
        int m = l;
        for(int i = l; i <= r; i++){
            if(nums[i]>nums[m])
                m = i;
        }
        TreeNode root = new TreeNode(nums[m]);
        root.left = getRoot(nums,l,m-1);
        root.right = getRoot(nums,m+1,r);
        return root;
    }
}

[weixueman]

辅助变量空间复杂度是o(1)没什么影响，又不是额外的数据结构

[touryung]

@Feyl 你这样循环体每次最大值都需要访问数组，从代码性能上来说还是用一个额外的变量来保存比较好（个人看法，大佬轻喷）(doge

[wying111]

@touryung 存下标每次访问也不需要多少性能

[huangpan2507]

每次找出的最大值构成一个只有root节点的树，那这些找出来的最大值做成的节点是怎么连成一棵树的呢？

[huangpan2507]

@ 我太粗心了，漏掉了 root.left=递归函数(0，最大值下标)
root.right=递归函数(最大值下标，len-1)

[iMinger]

大佬 YYDS

[AllenZzz0]

楼上那个超时的我也遇到了，是我以前copy别人的写法里面这个 buildTree(int[] preorder,int[] inorder){}方法的时候，这个preorder和inorder tmd反了，和测试样例正好参数反了。。 默认的是buildTree(int[] inorder, int[] postorder)，我一直提交超时，以为自己写的有问题 真是日了狗了

[CChappy2]

谢谢大佬！这里问题太绝了！

[JackHo327]

点赞+1
稍微有点小typo postorder和inorder写反了 瑕不掩瑜

[hzy4211]

东哥，想问为什么还要计算leftSize。比如在106题中，postorder数组中，为啥不可以用index？ root.left=self.build(inorder,inStart,index-1,postorder,postStart,index-1)
root.right=self.build(inorder,index+1,inEnd,postorder,index,postEnd-1)为啥这样不可以呀？

[labuladong]

@hzy4211 这个 index 是中序遍历结果 inorder 数组里面的索引，你不能直接用到后序遍历结果 postorder 里面的，所以要借助 leftSize 推导出在 postorder 里面的索引。

[PTLEI]

想问一下在前、后那题里面，root.right build的时候是不是postEnd需要 -1

[justdoit1013]

前序与中序构建二叉树这里

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return traverse(preorder, inorder, 0, 0, preorder.size()-1);
    }
    //在inorder中找preorder中的元素
    int findIndex(int elem, vector<int>& inorder){
        for(int i = 0; i < inorder.size(); i++)
            if(inorder[i] == elem)
                return i;
        return 0;
    }
    /**
    pos——preooder中元素索引
    l和h——inorder中子树区间
    */
    TreeNode* traverse(vector<int>preorder, vector<int> inorder, int pos, int l, int h){
        if(l > h)   return nullptr;
        int index;
        for(int i = l; i <= h; i++){
            index = findIndex(preorder[pos], inorder);
        }
        TreeNode* root = new TreeNode(preorder[pos]);
        //左子树待构建的结点个数
        int leftSize = index - pos;
        root->left = traverse(preorder, inorder, pos + 1, l, index - 1);
        root->right = traverse(preorder, inorder, pos + leftSize + 1, index + 1, h);
        //后序位置
        return root;
    }

这里root->right总感觉有问题，但改不出来，有些测试能过，有些过不了，像[1,2,3],[2,3,1]就过不了,会报栈溢出
root->right = traverse(preorder, inorder, pos + leftSize + 1, index + 1, h);

[zazazar]

前序中序构造二叉树不用新增数组的方法：

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder:
            return None
        rootvalue = preorder[0]
        root = TreeNode(rootvalue)

        leftsize = 0,0
        for index in range(len(inorder)):
            if inorder[index] == rootvalue:
                leftsize = index
                break
        
        root.left = self.buildTree(preorder[1:leftsize+1],inorder[:index])
        root.right = self.buildTree(preorder[leftsize+1:],inorder[index+1:])

        return root

[1mgroot]

为什么只有前后序的时候需要判断preStart == preEnd的情况，而前中序和后中序不需要单独写这个判断呢？

[lulaughing]

前中序：

• 如果写 preStart == preEnd 这个判断, 此时直接构造结点;
• 如果不写 preStart == preEnd 这个判断，再递归一次就会满足 preStart > preEnd, 并回退一栈, 再构造结点。

前后序：

• 如果不写 preStart == preEnd 这个判断，再递归一次不会满足 preStart > preEnd， 导致出错。

原因在于：

• 前中序：int index = map.get(rootVal);
• 前后序：int index = map.get(leftTreeRootVal);

后中序同理

[marianasignal]

class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder:
            return None
        
        root = TreeNode(preorder[0])
        n = inorder.index(root.val)

        root.left = self.buildTree(preorder[1:n+1], inorder[:n])
        root.right = self.buildTree(preorder[n+1:], inorder[n+1:])

        return root```

请问为啥105题不计算leftsize也可以通过

[jxs1211]

打卡

[GoingMyWay]

基于先序和中序的构造也可以这么写，逻辑上和大佬的思路是一样的。

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        index_map = {k: idx for idx, k in enumerate(inorder)}
        
        def build(left, right):
            if left >= right: return None
            
            node = TreeNode(preorder.pop(0))
            node.left = build(left, index_map[node.val])
            node.right = build(index_map[node.val]+1, right)
            return node
        return build(0, len(inorder))

[Youareblind]

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize)
{
    if(preorderSize == 0 || inorderSize == 0)
        return NULL;

    struct TreeNode *tree = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    int elem = preorder[0];

    int index = 0;
    while(inorder[index] != elem)
        index++;
    tree->val = elem;
    tree->left = buildTree(preorder + 1, index, inorder, index);
    tree->right = buildTree(preorder + index + 1, preorderSize - index - 1, inorder + index + 1, inorderSize - index - 1);

    return tree;
}

[NayelyA]

打卡

[AndyWu0107]

东哥，“后文 二叉树就那几个框架”的链接貌似错了，直接在这个网站搜索也搜不到这篇文章。

[labuladong]

没有问题，就是题目改了而已

[AndyWu0107]

感谢回复。我今天跟着本文敲了一遍代码，细细理解了一下，还是觉得“后文 二叉树就那几个框架”应该是博客园里这篇文章《二叉树的序列化，就那几个框架，枯燥至极》的内容，毕竟这里的上下文也在说前中后序的序列化结果的特点。这是我用搜索引擎搜出来的结果，在本站没搜到讲这个序列化与反序列化内容的文章。
然而文中的“后文 二叉树就那几个框架”点开之后，我这里跳转到的是题目不让我干什么，我偏要干什么，我没太理解它和本文的联系在哪里，盼解答。

[AndyWu0107]

不好意思我蠢了，刚发现本站下一篇就是讲序列化的文章。。。不过“后文 二叉树就那几个框架”的链接并没有指向这一篇，还是盼解答。

[Peter88645]

打卡

[bruceeewong]

20230114 打卡

[XinyaoQian1]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right


# valToIndex = {}
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        # i = 0
        # for _ in inorder:
        #     valToIndex[_] = i
        #     i+=1

        return self.build(preorder, inorder, 0, len(preorder)-1, 0, len(inorder)-1)
        
    # build 函数的定义：
    # 若前序遍历数组为 preorder[preStart..preEnd]，
    # 中序遍历数组为 inorder[inStart..inEnd]，
    # 构造二叉树，返回该二叉树的根节点 
    def build(self, preorder, inorder, preStart, preEnd, inStart, inEnd):
            # inStart, inEnd: inorder 的开始和结束
        # preStart, preEnd: preorder 的开始和结束
        
        
        # base case
        if preStart > preEnd:
            return None

    # root 节点对应的值就是前序遍历数组的第一个元素
        rootval = preorder[preStart]
    #  rootVal 在中序遍历数组中的索引
        # index = valToIndex.get(rootval)
        index = inorder.index(rootval)
        leftSize = index - inStart
        root = ListNode(rootval)
        
        # 分解到左右子树
        root.left = self.build(preorder, inorder, preStart+1, preStart + leftSize, inStart, index-1 )
        root.right = self.build(preorder, inorder,preStart+ leftSize+1 ,preEnd, index + 1,  inEnd)

        return root

[santakuu]

中序和后序遍历那题
if (inStart > inEnd) {
return null;
}

是怎么想到要做这个判断的呢，想不明白

[Yuchen-Song]

请问这里的build函数的base case为什么只用比较一个的start和end？不是传入了两对嘛？
还想问下最后一种情况为啥要加一个Start和End相等的case？

[rasasayang]

请问各位大佬一个问题，为什么前序和后序构造二叉树的时候多了这个判断？
if (preStart == preEnd) {
return new TreeNode(preorder[preStart]);
}

[CarlLy7]

因为这前序和后序构造二叉树这个算法中，我们使用了int leftRootVal = preorder[preStart + 1];来记录左子树的根节点。如果只有一个节点的时候也就是preStart==preEnd的时候就直接返回了，如果不加这个判断的话，我们在执行int leftRootVal = preorder[preStart + 1];的时候会出现数组越界问题。

[ZYHchasel]

python 总结一下三种构造方式，需要注意的是从前序后序恢复二叉树结构时，不仅指定了root，同时指定了左节点，因此在计算递归索引过程中，是左节点的索引：index+1，再加上指定的根节点是首位，因此在前序排列中左子树的索引为1 : index+2

根据前序中序恢复二叉树结构

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not (preorder or inorder):
            return None
        
        root = TreeNode(preorder[0])
        index = inorder.index(preorder[0])

        root.left = self.buildTree(preorder[1:index+1], inorder[:index])
        root.right = self.buildTree(preorder[index+1:], inorder[index+1:])
        
        return root

根据后序中序恢复二叉树结构

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not (inorder or postorder):
            return None
        
        root = TreeNode(postorder[-1])
        index = inorder.index(postorder[-1])
        
        root.left = self.buildTree(inorder[:index], postorder[:index])
        root.right = self.buildTree(inorder[index+1:], postorder[index:-1])
        
        return root

根据前序后续恢复二叉树结构

class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not(preorder and postorder):
            return None
        
        root = TreeNode(postorder[0])

        # 若二叉树只有一个节点，直接返回根节点
        if len(preorder) == 1:
            return root
        
        leftVal = preorder[1]
        # 与前面两种构造不同的是，这里的索引是左节点索引，而非根节点索引
        index = postorder.index(leftVal)

        root.left = self.constructFromPrePost(preorder[1:index+2], postorder[:index+1])
        root.right = self.constructFromPrePost(postorder[index+2:], postorder[index+1:-1])

[fairy3333]

有一个小问题，为什么base case中只需要判断一组start和end，而不是if (preStart>preEnd | | inStart>inEnd)呢，有没有uu回答一下555

[wuxiaoweisjz]

因为遍历得同一颗树啊,preStart与preEnd的差值和inStart与inEnd的差值相等,preStart>preEnd的条件下肯定数据也满足inStart>inEnd