chapter_divide_and_conquer/build_binary_tree_problem/

[giscus[bot]]

chapter_divide_and_conquer/build_binary_tree_problem/

动画图解、一键运行的数据结构与算法教程

https://www.hello-algo.com/chapter_divide_and_conquer/build_binary_tree_problem/

[danntee]

考研挺喜欢考这种题的

[krahets]

$i + 1 + m - l \ne m$ ，请仔细理解一下含义

[bushilao]

说错了，我把i + 1 + m - l 换成 m+1 也能跑通

[krahets]

换成 m+1 应该也不正确哦，可以试一下这个测试样例：

preorder = [3, 9, 5, 6, 2, 1, 7]
inorder = [5, 9, 6, 3, 1, 2, 7]

$i + 1 + m - l$ 的含义是：右子树的根节点在 preorder 中的索引，请对照图片推算一下

[syutengu]

读下来觉得这段是相对复杂，比较难理解的。
重点在<3. 基于变量描述子树区间>和<表 12-1 根节点和子树在前序遍历和中序遍历中的索引>。

首先一下创建四个指针imlr，要注意i单独活在pre世界，而其他三个活在in世界。

然后每一次左右递归，都需要分别取（当前根节点的）左右子树（的根节点）在pre中的索引值，作为dfs()的首个参数。

左子树（的根节点）在pre中的索引值很容易理解，因为它必须紧邻当前根节点的索引值，故 i+1 。

右子树（的根节点）在pre中的索引值应从 i+1 出发，再越过左子树的长度。
而其长度可以通过in中的两个指针 l 和 m 确定，即为 m-l 。
为什么是 m-l ? 因为规定in的结构为 "左 根 右"，故 根索引值 - 左子树（根）索引值 = 左子树长度。

不知道这样理解可以吗。

[lvmingxi2019]

中序+后序重建
class TreeNode:
def init(self, val:int, left=None, right=None):
self.val:int = val
self.left:TreeNode = left
self.right:TreeNode = right
def dfs(inorder:dict[int,int],postorder:list[int],rootpos:int,left:int,right:int)->TreeNode:
if left>right:
return None
root=TreeNode(postorder[rootpos])
mid=inorder[postorder[rootpos]]
root.right=dfs(inorder,postorder,rootpos-1,mid+1,right)
root.left=dfs(inorder,postorder,rootpos-1-(right-mid),left,mid-1)
return root
def buildTree(inorder: list[int], postorder: list[int]) -> TreeNode:
inorderdict={val:i for i,val in enumerate(inorder)}
return dfs(inorderdict,postorder,len(postorder)-1,0,len(inorder)-1)
if name == 'main':
inorder=[9,3,1,2,7]
postorder=[9,1,7,2,3]
root=buildTree(inorder,postorder)
print(root.val)
print(root.left.val)
print(root.right.val)
print(root.right.left.val)
print(root.right.right.val)

[zhuasdfg]

难点是如何把过程用编程语言表示出来，用指针把自己想要的操作表达出来，还得注意他们之间的约束关系

[BigDevil82]

一个小改进，dfs中没有用到inorder，可以去掉

[krahets]

谢谢建议，已优化

[Rzzzzzz]

k神, 如果把9去掉, 这个树退化成只有一边, 根节点就不存在左子树, 也就L的初始值不存在, i+1也不是左子树的根, 这个算法是不是就不适用了

[krahets]

不会的，这个算法适用于任意二叉树。建议运行源代码，改一下 test case 试试

[chenghui-ch]

还要用inorder限制左子树的范围（m-1），r-l<0了。

[newcakes]

用这种方式构建的树节点的值不能是一样的吧！因为map的key值必须唯一！
// 查询 m ，从而划分左右子树
int m = inorderMap[preorder[i]];
我想请教一下k佬，如果用unordered_multimap来实现树中结点的值可以是相同的，那该如何实现呢？
因为一个key值对应两个数组下标，该如何操作？还是说要另辟蹊径，用其他方式。

[newcakes]

c++语言呀！

[krahets]

你说的对。这道题目假设树中没有重复的节点，否则也无法完成划分了～

[mcthesw]

看理论部分感觉很难，但是代码实现居然如此简洁，这就是分治的魅力吗

[krahets]

递归代码一般都有这个特点～

[gh9991]

图12-8也太酷了吧，hhh，厉害

[xhddx]

root.left = dfs(preorder, inorderMap, i + 1, l, m - 1);
如果 左子树在inorder里的索引是[ l, m - 1], 那 这个i+1参数是什么含义呀，左子树的根节点在preOrder中的索引？ 也不对呀。这里没太理解

[xhddx]

哎呦，还真是左子树的根节点在preOrder中的索引

[amlei]

Hi, 请问有考虑添加：已知 后序和中序遍历 构建树的情形吗？我在构建时遇到下面一个问题，以本章后序遍历树为例：[9,1,7,2,3]

1. 以postorder or inorder 为索引？
   • 显然遵照后序遍历： [左子树 | 右子树 | 根节点] ，建立 inorder 索引后的 inorderMap 中直接能够找到根节点 ( postorderSize - 1 )，但对于其左子树与右子树来说本人无法得出如何获取它们的方式。
   • 以 postorder 建立索引，却丢失了根节点

[hpstory]

@amlei 力扣上面有类似的题目LeetCode 106 供参考

[chen-xiao-yu]

后序遍历的时候， [左子树 | 右子树 | 根节点]， 实际上可以说不成立(当然严格意义上说是成立的)。

比如你后序遍历出来的结果， 根节点是3， 前面 7，2并不是他的左节点和右节点。

因为实际上还有可能只有左子树或者右子树。

唯一能确定的只有中序遍历中，根节点的前一个节点是他的左节点，后序遍历最后一个节点是根节点。

至于有没有右节点，你还得看后续遍历中根节点的前一个节点和中序遍历中根节点的前一个节点是否一样，如果一样，说明没有右子树，如果不一样，才说明有右子树，这个时候紧挨着根节点的才是右节点。

[chen-xiao-yu]

哦，前面说那也都不对， 根节点前面一个节点也可能是他的左节点的右子树里面的节点

[amlei]

@hpstory 感谢给出的参考！ @chen-xiao-yu 感谢提供思路！
我结合本章的代码风格构建前序树的代码已实现，只需修改少部分即可实现：

dfs()函数:

// 子问题: 构建右子树
root->right = dfsPre(inorderMap, postorder, i - 1, m + 1, r, size);
// 子问题: 构建左子树
root->left = dfsPre(inorderMap, postorder, i - (r - m) - 1, l, m - 1, size);

build() 函数:

TreeNode *root = dfsPre(inorderMap, postorder, inorderSize - 1, 0, inorderSize - 1, inorderSize);

完整代码：

/* 构建二叉树-已知后序与中序 */
TreeNode *dfsPre(int *inorderMap, const int *postorder, int i, int l, int r, int size){
    // 子树区间为空时终止
    if (r - l < 0){
        return NULL;
    }

    // 初始化根节点, 以后序遍历的特性，最后一个元素即为根节点
    TreeNode *root = newTreeNode(postorder[i]);
    root->left = NULL;
    root->right = NULL;

    // 查询 m 从后序遍历索引到中序遍历，查看是否有左、右节点
    int m = inorderMap[postorder[i]];

    // 子问题: 构建右子树
    root->right = dfsPre(inorderMap, postorder, i - 1, m + 1, r, size);
    // 子问题: 构建左子树
    root->left = dfsPre(inorderMap, postorder, i - (r - m) - 1, l, m - 1, size);

    // 返回根节点
    return root;
}

// 构建前序树
TreeNode *buildTreePre(const int *inorder, int inorderSize, const int *postorder, int postorderSize){
    // 初始化哈希表，存储 inorder 元素到索引的映射
    int *inorderMap = (int *) malloc(sizeof(int) * MAX_SIZE);
    for (int i = 0; i < inorderSize; i++) {
        inorderMap[inorder[i]] = i;
    }

    TreeNode *root = dfsPre(inorderMap, postorder, inorderSize - 1, 0, inorderSize - 1, inorderSize);
    free(inorderMap);
    return root;
}

测试用例：

1. int inorder[] = {9,3,1,2,7}; int postorder[] = {9,1,7,2,3};
2. int inorder[] = {15,9,10,3,20,5,7,8,4}; int postorder[] = {15,10,9,5,4,8,7,20,3};

[eastcukt]

讲解很棒，也希望加些更详细的说明。比如这里中序是用来确定左右子树长度，进而在前序中确定左右子树(的根节点)下标。后序加中序重建也类似的道理。不过简洁点也好，要是当年在学数据结构时能看到hello算法就好了。。。

[krahets]

谢谢建议！

[Purdre]

/* 构建二叉树：分治 */
TreeNode *dfs(int *preorder, int *inorderMap, int i, int l, int r, int size) {
    // 子树区间为空时终止
    if (r - l < 0)
        return NULL;
    // 初始化根节点
    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    root->val = preorder[i];
    root->left = NULL;
    root->right = NULL;
    // 查询 m ，从而划分左右子树
    int m = inorderMap[preorder[i]];
    // 子问题：构建左子树
    root->left = dfs(preorder, inorderMap, i + 1, l, m - 1, size);
    // 子问题：构建右子树
    root->right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r, size);
    // 返回根节点
    return root;
}

思考不下去，没想明白它这个“递”的过程会怎样结束，就是可以知道如果左子树（右子树）为空的话就就不在进行构建左子树（右子树），比如当m-l=0时说明没有左子树了，就是在建立节点9的那个函数（也就是第二函数），里面还会有root->left=dfs(preoder,inorderMap,i+1,l,m-1,size)//此时i为2，l为0，m-1为0,很混乱。我的想法是需要在root->left=dfs(......)前面加if(m!=l)//如果相等代表左子树没了就不再进行。应该是还没没理解，所以来请教一下

[hpstory]

Hi @Purdre ，两种写法是一样的，TreeNode类型的左右节点默认值都是NULL，如果加if (m != l)，则当前节点的left会使用默认值NULL，如果不加，dfs返回的结果也是NULL。

[480284856]

在以3为根节点，递归到其左子树时，递归函数的中的部分参数为：

1. i=1
2. l=0
3. r=0

进入后，此时根节点为9，计算得到m=0.

再进行递归，进入节点9的左子树，此时递归函数中的部分参数为：

1. i=2
2. l=0
3. r=-1

[xxc111111]

12.3的代码有点难，如果有需要的小伙伴可以邮箱私我，我自己画了个步骤图，可以方便理解

[big-good-time]

好哥哥，180089009@qq.com

[akiradavidsong]

你好，我也觉得很难，麻烦发邮箱：512615045@qq.com，多谢！

[wrq6]

1620108097@qq.com谢谢

[Coolllh]

当前树是什么意思，没太看懂

[Coolllh]

public class BuildTree {
    /**
     *
     * @param preorder 二叉树的前序遍历结果
     * @param inorderMap 二叉树的中序遍历结果
     * @param rootInPre 要构建的子树根节点在前序遍历中的索引
     * @param left  要构建的子树的左子节点在中序遍历中的索引
     * @param right 要构建的子树的右子节点在中序遍历中的索引
     * @return  构建出的树根节点
     */
    public TreeNode dfs(int[] preorder, Map<Integer,Integer> inorderMap, int rootInPre, int left, int right){
        if (left>right){
            //左子节点的索引大于右子节点的索引，即无子节点
            return null;
        }
        TreeNode treeNode=new TreeNode();
        treeNode.val =preorder[rootInPre];
        //根节点在中序遍历中的索引
        int rootInIn=inorderMap.get(preorder[rootInPre]);
        treeNode.left=dfs(preorder,inorderMap,rootInPre+1,left,rootInIn-1);
        treeNode.right=dfs(preorder,inorderMap,rootInPre+1+rootInIn-left,rootInIn+1,right);
        System.out.println(treeNode);
        return treeNode;
    }

    public TreeNode buildTree(int[] preorder,int[] inorder){
        Map<Integer,Integer>inorderMap=new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i],i);
        }

        return dfs(preorder,inorderMap,0,0,inorder.length-1);

    }

    public static void main(String[] args) {
        new BuildTree().buildTree(new int[]{3,9,2,1,7},new int[]{9,3,1,2,7});
    }

}


    public TreeNode() {

    }


    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int value, TreeNode left, TreeNode right) {
        this.val = value;
        this.left = left;
        this.right = right;
    }

[Coolllh]

我根据这里的思路写了一个一样的，并且对其中的一些字段做上了注解，没注解刚看的时候有点一头雾水的

[Coolllh]

    public static void main(String[] args) {
        System.out.println(new BuildTree().buildTreeByPost(new int[]{8, 6, 9, 1, 7, 2, 3}, new int[]{8, 9, 6, 3, 1, 2, 7}));
    }



    public TreeNode buildTreeByPost(int[] postorder,int[] inorder){
        Map<Integer,Integer> inorderMap=new HashMap<>();
        System.out.println(Arrays.toString(inorder));
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i],i);
        }
        System.out.println(inorderMap);
        return  dfsPost(postorder,inorderMap,postorder.length-1,0,inorder.length-1);
    }

    /**
     *
     * @param postorder 后序遍历的结果
     * @param inorderMap 中序遍历的结果Map集合
     * @param rootInPost 要构建的树的根节点在后续遍历中的索引
     * @param left  要构建的树的最左子节点在中序遍历中的索引
     * @param right 要构建的树的最右子节点在中序遍历中的索引
     * @return 要构建的树的根节点
     */
    public TreeNode dfsPost(int[] postorder,Map<Integer,Integer> inorderMap,int rootInPost,int left,int right){
       if (left>right) return null;

        TreeNode treeNode=new TreeNode();

        treeNode.val=postorder[rootInPost];
        //根节点在中序遍历中的索引
        int rootInIn=inorderMap.get(postorder[rootInPost]);
        //右子树节点的数量
        int rightTreeNodeNum=right-rootInIn;
        treeNode.left=dfsPost(postorder,inorderMap,rootInPost-rightTreeNodeNum-1,left,rootInIn-1);
        treeNode.right=dfsPost(postorder,inorderMap,rootInPost-1,rootInIn+1,right);
        return treeNode;
    }

[Coolllh]

昨天看到评论区有一个写了中序+后序的，我就想着自己也试着写一下，和前序+后序的思路是一样的，
写完这个中序+后序的感觉对构件树的递归过程有了一些想法

[Coolllh]

我认为递归构建树，每一次递归，他的目的实际上只是为了构建一个节点，调用一次dfs方法实际上只构建了一个节点，给这个节点的value属性左子节点，右子节点都填上对应的属性，最后返回到最外层的时候，实际上得到的就是最上方的根节点，而且构建树的过程我想应该中序遍历是必备的，因为没有中序遍历则无法分辨出左子树和右子树，前序和后序遍历的区别我想应该就是在，先遍历根节点还是最后遍历根节点，k神能指点一下我说的对不QWQ

[Asunami]

如果二叉树中有值重复的节点的情况该如何实现呢

[ghost]

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function buildTree(preorder, inorder) {
  if (preorder.length === 0) {
    return null;
  }
  let root = new TreeNode(preorder[0]);
  let index = inorder.indexOf(preorder[0]);
  root.left = buildTree(preorder.slice(1, index + 1), inorder.slice(0, index));
  root.right = buildTree(preorder.slice(index + 1), inorder.slice(index + 1));
  return root;
}

[ghost]

我损失一点空间[汗]

[nors1993]

这章脑子有点不够用了~这么建树的意义是什么？有没有大佬用简单易懂的话给指点一下？

[Coolllh]

鹅，这是题目的要求就是根据一个二叉树的前序遍历和中序遍历的结果，来还原这个二叉树

[krahets]

我觉得主要意义是让我们更加透彻地理解二叉树和它的前序遍历、中序遍历的关系是什么

[syutengu]

知道2-1=1，可以进一步理解1+1=2。
解构前中后序遍历并建构树，以更好地理解解构树并建构前中后序遍历。
树、数组、前中后序，这些都不是目的，
只是为了“从心所欲不逾矩”地“表示”数据，
心之所欲，利之所在。

[syutengu]

尤长，概括为三字：
我愿意。

[panumat]

试了下举一反三，由前序加后序来还原二叉树，发现无法实现，因为在链表情况下，不借助中序遍历序列无法确定树的左右偏情况，必须由中序加上前序后续二者其一才能反推二叉树

[travonf]

数据结构课上有讲，前序和后序无法确定一个树。

[PotatoSmith]

前中后序遍历 豁然开朗了

[shuMuXieMing]

不是很理解，为什么左子树是 “i+1"，如果左子树不只是一个节点，还能用”i+1“吗？

[shuMuXieMing]

知道了，i+1 只是左子树的根节点

[Clemna10]

好精妙，每一个子树的前序遍历的首元素就是子树的根节点， 然后找出这个根节点在中序遍历的位置，以该根节点为基准继续划分下一个左右子树