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]

谢谢哈~

[Ares-bit]

给没看明白的朋友们推导下:
设满二叉树高度为h，总结点数为n，则有A：n = 2^(h+1) - 1
又知满二叉树最下层的叶子结点个数为：2^h
故由A可知2^h = (n + 1) / 2

[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]

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

[travonf]

广度优先搜索用队列，深度优先搜索用栈，递归也是用的栈。

[liuyanqing1023]

这是来自QQ邮箱的假期自动回复邮件。   您好，我最近正在休假中，无法亲自回复您的邮件。我将在假期结束后，尽快给您回复。

[pyj1971341376]

这里可以写一下迭代实现的前、中、后序遍历。呼应一下开头(迭代和递归)提到的关于迭代实现解决某些问题相比较递归解决更晦涩难懂的观点。

[huxiaoning]

迭代实现来一份：
/* 前序遍历 */
void preOrder(TreeNode root) {
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
list.add(node.val);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}

/* 中序遍历 */
void inOrder(TreeNode root) {
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        // 将当前节点及其左子节点入栈，直至左子树为空
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        // 弹出栈顶节点并访问
        curr = stack.pop();
        list.add(curr.val);

        // 将右子树设为当前节点，继续遍历右子树
        curr = curr.right;
    }
}

/* 后序遍历 */
void postOrder(TreeNode root) {
    stack.push(root);
    Stack<Integer> result = new Stack<>();

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.push(node.val);

        if (node.left != null) {
            stack.push(node.left);
        }
        if (node.right != null) {
            stack.push(node.right);
        }
    }

    // 输出后序遍历结果
    while (!result.isEmpty()) {
        list.add(result.pop());
    }
}

[maskercyh]

深度优先算法提供的示例是不是都有问题，好像没有声明list，不该在参数中声明一下吗？

[Than-Sing]

NOTE：在python里面，判断deque非空用while deque比while len(deque)更快

[Asce-ops]

def level_order(root: TreeNode | None) -> list[int]:
"""层序遍历"""
# 初始化队列，加入根节点
queue: deque[TreeNode] = deque()
queue.append(root)
# 初始化一个列表，用于保存遍历序列
res = []
while queue:
node: TreeNode = queue.popleft() # 队列出队
res.append(node.val) # 保存节点值
if node.left is not None:
queue.append(node.left) # 左子节点入队
if node.right is not None:
queue.append(node.right) # 右子节点入队
return res
层序遍历的时候不应该上来就把root入队吧，万一root传的是None出队之后就要报错了，还是是如果队列中只有一个None while queue在判断的时候会为假？

[tstanon]

// 前序遍历, idx用于递归时确定下一个结果存放在结果数组什么位置
void pre_traversal_rec(TreeNode *root, float* arr, int* idx){ if (!root) return ; arr[(*idx)++] = root->val; pre_traversal_rec(root->left, arr, idx); pre_traversal_rec(root->right, arr, idx); }
void pre_traversal_nrec(TreeNode *root, float* arr, int size){
   if (!root) return ; int top = -1, idx = 0; TreeNode **stack = (TreeNode **)malloc(sizeof(TreeNode*) * size); stack[++top] = root;
   // 出栈，获取节点值，入栈右左子节点，直到栈为空
   while (top >= 0){ TreeNode *node = stack[top--]; arr[idx++] = node->val; if (node->right) stack[++top] = node->right; if (node->left) stack[++top] = node->left; }
}
// 中序遍历
void in_traversal_rec(TreeNode *root, float *arr, int *idx){ if (!root) return ; in_traversal_rec(root->left, arr, idx); arr[(*idx)++] = root->val; in_traversal_rec(root->right, arr, idx); }
void in_traversal_nrec(TreeNode *root, float *arr, int size){
   if (!root) return; int top = -1, idx = 0; TreeNode **stack = (TreeNode **)malloc(sizeof(TreeNode*) * size);  TreeNode *cur = root;
   // 1. 压栈的同时，将当前指针移动到最左边的节点。2. 出栈，获取节点值。 3. 将指针移动到右子节点。循环1-3直到栈为空。
   while (top >=0 || cur){ 
      while (cur) { stack[++top] = cur; cur = cur->left; } 
      cur = stack[top--]; arr[idx++] = cur->val; cur = cur->right;
   }
}
// 后序遍历
void post_traversal_rec(TreeNode *root, float *arr, int *idx){ if (!root) return; post_traversal_rec(root->left, arr, idx); post_traversal_rec(root->right, arr, idx); arr[(*idx)++] = root->val; }
// 非递归方法1：使用栈+上次访问标记
void post_traversal_nrec(TreeNode *root, float *arr, int size) {
   if (!root) return; int top = -1, idx = 0; 
   TreeNode **stack = (TreeNode **)malloc(sizeof(TreeNode*) * size), *cur = root, *lastVisited = NULL; // lastVisited 用于记录上一个访问的节点
   // 1. 压栈的同时，将当前指针移动到最左边的节点。2. 如果右子节点存在且未被访问过，则将指针移动到右子节点。3. 否则，出栈，获取节点值。4. 记录上一个访问的节点。循环1-4直到栈为空。
   while (top >=0 || cur){
      while(cur) {stack[++top] = cur; cur = cur->left; } cur = stack[top]; 
      if (cur->right && cur->right != lastVisited) { cur = cur->right; }
      else { arr[idx++] = cur->val; lastVisited = cur; top--; cur = NULL; }
   }
}
// 非递归方法2：使用双栈
void post_traversal_nrec2(TreeNode *root, float *arr, int size){
   if (!root) return; int top1 = -1, top2 = -1, idx = 0; 
   // 栈1用于存储节点，栈2用于存储栈1出栈的节点。栈1出栈的顺序是根右左，栈2出栈的顺序是左右根。
   TreeNode **stack1 = (TreeNode **)malloc(sizeof(TreeNode*) * size), **stack2 = (TreeNode **)malloc(sizeof(TreeNode*) * size); stack1[++top1] = root;
   // 遍历栈1，将节点出栈，存入栈2， 入栈左右子节点。
   while (top1 >= 0){ TreeNode *node = stack1[top1--]; stack2[++top2] = node; if (node->left) stack1[++top1] = node->left; if (node->right) stack1[++top1] = node->right; }
   // 遍历栈2，将节点出栈，存入结果数组。
   while (top2 >= 0) arr[idx++] = stack2[top2--]->val;
}

[tstanon]

二叉树的前中后序遍历的递归和非递归C语言版本代码

// 前序遍历, idx用于递归时确定下一个结果存放在结果数组什么位置
void pre_traversal_rec(TreeNode *root, float* arr, int* idx){ if (!root) return ; arr[(*idx)++] = root->val; pre_traversal_rec(root->left, arr, idx); pre_traversal_rec(root->right, arr, idx); }
void pre_traversal_nrec(TreeNode *root, float* arr, int size){
   if (!root) return ; int top = -1, idx = 0; TreeNode **stack = (TreeNode **)malloc(sizeof(TreeNode*) * size); stack[++top] = root;
   // 出栈，获取节点值，入栈右左子节点，直到栈为空
   while (top >= 0){ TreeNode *node = stack[top--]; arr[idx++] = node->val; if (node->right) stack[++top] = node->right; if (node->left) stack[++top] = node->left; }
}
// 中序遍历
void in_traversal_rec(TreeNode *root, float *arr, int *idx){ if (!root) return ; in_traversal_rec(root->left, arr, idx); arr[(*idx)++] = root->val; in_traversal_rec(root->right, arr, idx); }
void in_traversal_nrec(TreeNode *root, float *arr, int size){
   if (!root) return; int top = -1, idx = 0; TreeNode **stack = (TreeNode **)malloc(sizeof(TreeNode*) * size);  TreeNode *cur = root;
   // 1. 压栈的同时，将当前指针移动到最左边的节点。2. 出栈，获取节点值。 3. 将指针移动到右子节点。循环1-3直到栈为空。
   while (top >=0 || cur){ 
      while (cur) { stack[++top] = cur; cur = cur->left; } 
      cur = stack[top--]; arr[idx++] = cur->val; cur = cur->right;
   }
}
// 后序遍历
void post_traversal_rec(TreeNode *root, float *arr, int *idx){ if (!root) return; post_traversal_rec(root->left, arr, idx); post_traversal_rec(root->right, arr, idx); arr[(*idx)++] = root->val; }
// 非递归方法1：使用栈+上次访问标记
void post_traversal_nrec(TreeNode *root, float *arr, int size) {
   if (!root) return; int top = -1, idx = 0; 
   TreeNode **stack = (TreeNode **)malloc(sizeof(TreeNode*) * size), *cur = root, *lastVisited = NULL; // lastVisited 用于记录上一个访问的节点
   // 1. 压栈的同时，将当前指针移动到最左边的节点。2. 如果右子节点存在且未被访问过，则将指针移动到右子节点。3. 否则，出栈，获取节点值。4. 记录上一个访问的节点。循环1-4直到栈为空。
   while (top >=0 || cur){
      while(cur) {stack[++top] = cur; cur = cur->left; } cur = stack[top]; 
      if (cur->right && cur->right != lastVisited) { cur = cur->right; }
      else { arr[idx++] = cur->val; lastVisited = cur; top--; cur = NULL; }
   }
}
// 非递归方法2：使用双栈
void post_traversal_nrec2(TreeNode *root, float *arr, int size){
   if (!root) return; int top1 = -1, top2 = -1, idx = 0; 
   // 栈1用于存储节点，栈2用于存储栈1出栈的节点。栈1出栈的顺序是根右左，栈2出栈的顺序是左右根。
   TreeNode **stack1 = (TreeNode **)malloc(sizeof(TreeNode*) * size), **stack2 = (TreeNode **)malloc(sizeof(TreeNode*) * size); stack1[++top1] = root;
   // 遍历栈1，将节点出栈，存入栈2， 入栈左右子节点。
   while (top1 >= 0){ TreeNode *node = stack1[top1--]; stack2[++top2] = node; if (node->left) stack1[++top1] = node->left; if (node->right) stack1[++top1] = node->right; }
   // 遍历栈2，将节点出栈，存入结果数组。
   while (top2 >= 0) arr[idx++] = stack2[top2--]->val;
}

[Yojay97]

想问一下大佬，前中后序遍历是约定俗称的遍历方式嘛？我们在学习的时候，就是只需要记住遍历的顺序和实现方法就好了吗？

[shenyv1]

这几个序的意思是根节点的顺序，前序就是根节点在前面，根，左，右，去访问，中序就是左，根，右，后续就是左，右，根，左右顺序无所谓一般先左后右，主要是根节点顺序。能看懂就看文档，看不懂搜视频

[akiradavidsong]

空间复杂度：在最坏情况下（树完全倾斜到一边），空间复杂度为 O(n)，因为递归调用栈的深度可能达到 n。在平衡树的情况下，空间复杂度为 O(log n)。

[OrangeAlien]

如果广度优先遍历的函数只返回一个列表，而不是访问节点值并打印的话，可以考虑原地的算法不用辅助队列。只用双指针也可以，快指针用来向数组尾部添加左右子树，慢指针指向当前访问的节点，当快慢指针重合时停止，返回列表

[Ares-bit]

是的，按照根的访问顺序来分，只有这三种，要么根先，要么根中，要么根后，但是对于这三种遍历中的任意一种，你也可以从右子树遍历，这样你的前序遍历顺序就是：根右左。 我觉得作者画的区分前中后三种遍历的那个图不错，看一眼就忘不了 Yojay97 ***@***.***> 于2024年10月3日周四 11:49写道：

…

想问一下大佬，前中后序遍历是约定俗称的遍历方式嘛？我们在学习的时候，就是只需要记住遍历的顺序和实现方法就好了吗？ — Reply to this email directly, view it on GitHub <#25 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ANN3UQD23D4I77FTGH673QTZZS5FRAVCNFSM6AAAAAASLXLDJWVHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTAOBSG4ZDMNY> . You are receiving this because you commented.Message ID: ***@***.***>

[FrierenGreatDemonLord]

Python 迭代法

def preorderTraversal(root: TreeNode) -> list[int]:
    ret, s = [], []
    while s or root:
        if root:
            ret.append(root.val)
            s.append(root)
            root = root.left
        else:
            root = s.pop().right
    return ret


def preorderTraversal(root: TreeNode) -> list[int]:
    ret, s = [], []
    while s or root:
        if root:
            s.append(root)
            root = root.left
        else:
            root = s.pop()
            ret.append(root.val)
            root = root.right
    return ret


def postorderTraversal(root: TreeNode) -> list[int]:
    ret, s = [], []
    while s or root:
        while root:
            ret.insert(0, root.val)
            s.append(root)
            root = root.right
        root = s.pop().left
    return ret

[wyz609]

想弄懂递归的内部实现原理

[kingleonardo999]

以下是C++的迭代遍历树的代码（如果有问题，或者有可以优化的地方敬请指正）该代码是我基于学校数据结构和算法基础课程的C语言代码修改的，后序遍历的迭代算法有两种实现：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val, TreeNode *left, TreeNode *right) {
        this->val = val;
        this->left = left;
        this->right = right;
    }
    TreeNode(int val):left(nullptr), right(nullptr){this->val = val;}
};

vector<int> preOeder(TreeNode *root){
    vector<int> vec;
    stack<TreeNode *> s; // 深度优先遍历到底层后需要回溯，回溯时由底层向上层，先进后出，故采用栈存储
    if(!root) return vec;
    s.push(root);
    while(!s.empty()){
        TreeNode *curr = s.top();
        vec.push_back(curr->val); // 这里表示先访问了根节点
        s.pop();
        // 这里压栈的顺序要注意，栈是先进后出的，因此应该先压右子树
        if(curr->right){
            s.push(curr->right);
        }
        if(curr->left){
            s.push(curr->left);
        }
    }
    return vec;
}

vector<int> inOrder(TreeNode *root){
    vector<int> vec;
    stack<TreeNode *> s;
    if(!root) return vec;
    TreeNode *curr = root;
    while(!s.empty() || curr){ // 增加curr判断条件，因为遍历了根节点后栈为空，但此时右子树尚未遍历，此时curr为右子树的根节点
        // 先把当前根节点的左子树遍历了
        while(curr){
            s.push(curr);
            curr = curr->left;
        }
        curr = s.top(); // 左子树遍历完毕，这里可以访问根节点
        vec.push_back(curr->val);
        s.pop();
        // 转向处理右子树
        curr = curr->right;
    }
    return vec;
}

// 双栈法
vector<int> postOrder1(TreeNode *root){
    vector<int> vec;
    stack<TreeNode *> s1; // 用于存储待处理根节点的左右节点
    stack<TreeNode *> s2; // 用于存储根节点，用于反转输出顺序
    if(!root) return vec;
    s1.push(root);
    while(!s1.empty()){
        TreeNode *curr = s1.top();
        s1.pop();
        s2.push(curr); // 此时curr就是一个根节点，直接入栈s2
        // 先入s2表示后输出，因此s1先入左子树节点，再入右子树节点，保证取出curr时是右子树节点先入s2
        if(curr->left){
            s1.push(curr->left);
        }
        if(curr->right){
            s1.push(curr->right);
        }
    }
    // 取出s2的元素赋值给vec
    while(!s2.empty()){
        TreeNode *node = s2.top();
        s2.pop();
        vec.push_back(node->val);
    }
    return vec;
}

// 一个栈+状态
vector<int> postOrder2(TreeNode *root){
    vector<int> vec;
    stack<TreeNode *> s;
    if(!root) return vec;
    TreeNode *curr = root;
    TreeNode *lastVisited = nullptr; // 记录最近访问过的节点
    while (!s.empty() || curr)
    {
        // 先将根节点及其左子树压入栈
        while(curr){
            s.push(curr);
            curr = curr->left;
        }
        curr = s.top();
        // 如果当前节点的右子树为空或者已经被访问，则访问该节点
        if(!curr->right || curr->right == lastVisited){
            s.pop();
            vec.push_back(curr->val);
            lastVisited = curr; // 更新被访问的节点
            curr = nullptr; // 准备弹出下一个节点
        } else{
            // 转向处理右子树
            curr = curr->right;
        }
    }
    return vec;
}