chapter_tree/binary_tree_traversal/

[giscus[bot]]

chapter_tree/binary_tree_traversal/

一本动画图解、能运行、可提问的数据结构与算法入门书

https://www.hello-algo.com/chapter_tree/binary_tree_traversal/

[Slone123c]

点进去好像没有看见go的代码显示？ 想知道有没有机会贡献go的代码

[krahets]

哈喽，感谢您哇～你可以关注这个 issue ，Go 代码有 Reanon 同学在翻译了，还剩一章～我会尽快把 Go 代码贴到文章中

[gltianwen]

结点总数为 n 的二叉树的高度 Log2(n+1) - 1

[gltianwen]

所谓的前中后序遍历：先遍历父节点为preOrder，第二个遍历父节点为inOrder，最后遍历父节点为postOrder

[L-Super]

遍历方式：

• 前序遍历（先根，再左，最后右）
• 中序遍历（先左，再根，最后右）
• 后序遍历（先左，再右，最后根）

[zh-h]

用栈实现 dfs

[imarman]

这里的前中后序，指的是根结点吧

[krahets]

确实，含义是“根结点在何时被访问”

[yuelinxin]

问：为什么DFS遍历二叉树有前、中、后三种顺序，分别有什么用呢？

[yuelinxin]

答：DFS的前、中、后序遍历和访问数组的顺序类似，是遍历二叉树的基本方法，利用这三种遍历方法，我们可以得到一个特定顺序的遍历结果。

[krahets]

补充：例如在二叉搜索树中，由于结点大小满足 左子结点值 < 根结点值 < 右子结点值 ，因此我们只要按照 左 -> 根 -> 右 的优先级遍历树，即可获得有序序列。而这种优先级对应的正是「中序遍历」

[fallenleavesguy]

举个例子，UI结构一般是树结构，显示的层叠顺序，开发者采用的访问顺序不一样，会影响哪个元素会最后显示在最上面，即最后访问并渲染的那个元素。很多时候访问顺序产生不一样的程序结果

[chenwenstar]

递归利用栈的数据结构，代码的真少啊

[chen8866]

为啥没有c的代码，描述数据结构最好的代码就是c啊

[krahets]

呜呜，会尽快添加 C 语言版本的

[viogami]

你这个前、中、后序遍历的图简直太好了，把我至今抽象的理解具现化了 ❤️

[krahets]

这张图画了很久！哈哈哈

[fjiangfan]

真的，这张图太优美了，一个在我看来只能用动态图展示的道理用静态的形式就绝佳地呈现了出来，优雅！:bow:

[Telly-S]

binary_tree_bfs.c

/* 辅助队列 */
queue = (TreeNode **)malloc(sizeof(TreeNode) * MAX_NODE_SIZE);
这里的malloc是不是应该写为sizeof(TreeNode*) * MAX_NODE_SIZE呢？因为数组里面存的好像都是指针。

[Gonglja]

是的，queue中存储的为指针（在外部已经 malloc ），所以此处仅需为指针分配空间，也就是 sizeof(TreeNode *) * MAX_NODE_SIZE

[ronalgao]

空间复杂度：在最差情况下，即满二叉树时，遍历到最底层之前，队列中最多同时存在 （N+1）/2个节点——满二叉树，bfs遍历到最底层之前，队列中的节点就是叶节点2的h次方吧？

[krahets]

是的，拿高度 h = 2 的满二叉树举例，节点总数 n = 7 ，易得底层节点数量 = 2^h = (n + 1) / 2

[ronalgao]

谢谢哈~

[bukexiusi]

太牛啦，每次面试都需要复习一遍，这次永远不会忘记了

[WhiteRhinos]

前序遍历结合栈使用迭代

public void preOrder2(TreeNode root)
    {
        // 创建栈,加入根节点
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty())
        {
            TreeNode pop = stack.pop();
            System.out.println(pop.data);
            if (pop.right!=null)
            {
                stack.push(pop.right);
            }
            if (pop.left!=null)
            {
                stack.push(pop.left);
            }

        }

    }

[zhuasdfg]

牛哇，我结合画图才看明白，感觉栈比队列复杂一点，脑子有点转不过来

[WhiteRhinos]

队列是怎么实现前序遍历的

[is-liu]

用双向队列可以前序遍历，不过也是利用栈的思想，单纯的队列在我的认知里不能。
前序遍历的顺序是 根结点 -> 左子树 -> 右子树，如果左子树深度不为0会继续以这个顺序来查找左子树，直到左子树为空才会查找右子树。
广度优先搜索是逐层查找，只要深度相同即使两个结点的父节点不同也会一起查找。这就和前序遍历的顺序相违背

[zhuasdfg]

太棒了，对递归了解更多了一点，其他的广度优先和深度优先遍历是不是也用递归

[zhuzilv]

想问一下，你们在写回溯的时候，大脑里真的会有比较健全的逻辑吗，我思路总断，看着代码很简单，就是要想很久，想的很累

[MaoPingZou]

我也一样，应该还是缺少练习了，后面多刷刷题应该记得更牢

[ryanzhouff]

所谓一图胜千言，用图来展示函数递归调用的过程。

在JavaScript中，函数调用会创建一个函数执行上下文(execution context)，这个执行上下文会在调用栈中(call stack)维护，简单来说，就是调用函数的时候，函数会被放到栈的顶部，函数执行完毕就从栈顶移除。

假设二叉树结构如图：

这里以中序遍历为例。

当调用tree.inOrder(root)，inOrder(node11)函数入栈，此时结点是根节点，用node11表示，11表示结点的值，此时调用栈如下：

inOrder(node11)中又调用inOrder(node7)，所以inOrder函数再次入栈，调用栈结构如下：

以此类推，直到结点为空，此时调用栈结构如下：

当执行inOrder(null);，函数执行完毕，从调用栈中移除，并返回到调用它的位置。
接着调用下一行语句console.log(3)，在控制台输出3。接着调用下一行语句，即inOrder(null)，入栈，执行完毕之后出栈，此时，inOrder(node3)执行完毕，从栈顶弹出。

开始执行inOrder(node5)，其过程和执行inOrder(node3)类似，执行结束之后，从栈中弹出，并开始执行inOrder(node7)，在输出7之后，执行inOrder(node8)，入栈，因为node8没有子节点，所以它会在输出8之后，从栈顶弹出，此时inOrder(node7)也执行完毕。

最后执行inOrder(node11)，过程和inOrder(node7)类似，输出11，然后执行inOrder(node12)，因为node12也没有子节点，所以它在输出12之后，从栈顶弹出。此时inOrder(node11)执行完毕，从栈顶弹出。到此，整个递归过程结束。

最终输出结果：3, 5, 7, 8, 11, 12

前序遍历和后序遍历的递归过程类似。

[Moayzwdbb]

牛哇牛哇

[blueFiveOvO]

听老师上课讲完后在配合这张图看前中后序遍历，效果翻倍😆

[Richardxm2062]

用python3.9.13版本执行chapter_tree文件下的python文件 都会遇到各种报错 最典型的是 ListNode | None 这类代码TypeError
似乎在当前版本的python并不支持返回值 的 | 运算？ 你们都能正确执行代码嘛。我看在线预览所使用的是python3.11版本，真是需要最新版本的python才能正确运行吗

[krahets]

Hi，是的，书中的 Python 代码使用了最新的 type hints 语法，请在 Python >= 3.10 环境下运行

[Richardxm2062]

我安装了3.11 确实都可以执行了。哎 但是考试环境都是3.9 -，-

[krahets]

收到～书中写出来是为了提升代码的可读性，采用最新的 type hints 是因为其更简洁。应该不用太担心版本问题，原因有：

1. 3.9 和 3.10 在绝大部分场景下的用法都是一致的（在一般使用中甚至很难找到不同点）；
2. 平时写 Python 代码时可以不写 type hints ；

[FortuneBush]

请问大佬，为什么C++的二叉树遍历的代码实现中都要传入TreeNode *root，直接传入TreeNode root可以吗？为什么要在这里传入指针呀？

[krahets]

Hi，对于节点这类对象实例，我们习惯用指针操作，主要原因有：

1. 避免不必要的复制：当你直接传递一个对象给函数时，C++ 默认会创建该对象的一个副本。这不仅会增加内存使用，还会增加额外的性能开销。
2. 允许修改原始数据：当你传递一个对象的指针给函数时，你实际上是传递了一个指向原始对象的引用。这使得函数能够直接修改原始对象。如果直接传入 TreeNode root ，则在函数内只能修改节点的副本了。

[MoCHEN-WHU]

使用递归形式实现前/中/后序遍历在树很深的时候会有性能问题吗？感觉是不是可以用栈替代递归实现。还是说只有前序用栈实现比较直观

[krahets]

不会～实际上，显示地用栈来实现，可能会更慢。要相信现代编译器的优化能力，我们需要做的是写出逻辑清晰、语义明确的代码

[luttons]

这个 前、中、后序遍历的图实在是太太太太形象了！！！！

[lucienshawls]

根左右，左根右，左右根
DNA动了

[lovelock]

之前在B站看到过一个小姐姐讲的关于前中后序遍历的意义。有几个重点

1. 所谓前中后，指的是每层的“根节点”
2. 遍历一定是先左后右的，所以前中后序分别是：中左右、左中右、左右中
3. 写迭代写法的时候可能会发现为什么是node.right先入栈，这是因为栈的特性，你想让node.left先出栈，只能让它后入栈
4. 在写迭代写法的时候有同学可能发现，为什么后序遍历还要反转一下才行，那是因为当我们会写了“中左右”，其实就已经会写了“中右左”，而后序遍历的“左右中”正好是“中右左”的反转

3月份刚开始学，一点小的体会但愿能帮助到新同学。

[Lijingwoquan]

哈哈 我也看见过 这个记法很好

[summer-breeze123]

听君一席话，胜读十年书。昨天用AI生成了一个后序遍历，疑惑了半天为什么最终结果是反的，到你这里懂了。

[RENHJa]

请问作者，这个遍历函数里面的vec没有定义，在实际编程中应该在哪里定义呢？

void preOrder(TreeNode *root) {
    if (root == nullptr)
        return;
    // 访问优先级：根节点 -> 左子树 -> 右子树
    vec.push_back(root->val);
    preOrder(root->left);
    preOrder(root->right);
}

[dailegedai]

可以参考层序遍历中的定义，vectorvec;

[dailegedai]

这里应该有用尖括号括起来的int,不知道为什么显示不出来

[RENHJa]

我试过，像层序遍历一样在函数内部定义vec是不行的，因为这个深层优先的遍历用到递归，每次递归都会新建一个vec，无法保存之前遍历过的节点。后来我想到把vec定义成全局的就行了，在函数外面定义

[krahets]

文章中的代码仅展示核心部分，请前往代码仓库下载源代码，可一键运行：
https://github.com/krahets/hello-algo

[Autumn00air]

图7-10真的妙啊~之前上数据结构的时候经常容易搞混，这个图让我恍然大悟

[moonpoet]

非常清晰

[zjt666666zjt]

[krahets]

具体哪里错了？

[AllofMortal]

广度优先遍历通常借助“队列”来实现。队列遵循“先进先出”的规则，而广度优先遍历则遵循“逐层推进”的规则，两者背后的思想是一致的。
这句话有些费解，而后面应该翻转但是依然是广度优先遍历

[EOMZON]

关于层序遍历今天学习时想到的拟人例子:
想像二叉树为一个大家族族谱(每一个人最多有两个孩子),按照这个族谱从上到下,从左到右依次拜访
但是不认识任何一位,只能从最上面的长辈开始
你有一个笔记本,可以用它记录找到的名字,先将唯一的名字写在笔记本上,去拜访这位长辈
找到这位长辈之后,你可以把ta的名字划掉,并记录上ta孩子的名字(每个人只会告诉你他的孩子是谁)
接着去询问下一位笔记本上的名字,划掉并记录ta的孩子(如果有的话)
直到本子上没有可以去拜访和记录孩子
上述笔记本记录的过程是先记录的先划掉,先进先出与队列的机制完全一样,所以用队列作为数据结构