用迭代法编写二叉树的前后中序遍历案例

二叉树的迭代遍历

看完本篇大家可以使用迭代法，再重新解决如下三道leetcode上的题目：

144.二叉树的前序遍历

94.二叉树的中序遍历

145.二叉树的后序遍历

为什么可以用迭代法（非递归的方式）来实现二叉树的前后中序遍历呢？

我们在栈与队列：匹配问题都是栈的强项中提到了，递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

此时大家应该知道我们用栈也可以是实现二叉树的前后中序遍历了。

前序遍历（迭代法）

我们先看一下前序遍历。

前序遍历是中左右，每次先处理的是中间节点，那么先将跟节点放入栈中，然后将右孩子加入栈，再加入左孩子。

为什么要先加入右孩子，再加入左孩子呢？因为这样出栈的时候才是中左右的顺序。

动画如下：

不难写出如下代码: （注意代码中空节点不入栈）

class Solution {
public:
    vector preorderTraversal(TreeNode* root) {
        stack st;
        vector result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();                       // 中
            st.pop();
            result.push_back(node->val);
            if (node->right) st.push(node->right);           // 右（空节点不入栈）
            if (node->left) st.push(node->left);             // 左（空节点不入栈）
        }
        return result;
    }
};

此时会发现貌似使用迭代法写出前序遍历并不难，确实不难。

此时是不是想改一点前序遍历代码顺序就把中序遍历搞出来了？

其实还真不行！

但接下来，再用迭代法写中序遍历的时候，会发现套路又不一样了，目前的前序遍历的逻辑无法直接应用到中序遍历上。

中序遍历（迭代法）

为了解释清楚，我说明一下刚刚在迭代的过程中，其实我们有两个操作：

处理：将元素放进result数组中

访问：遍历节点

分析一下为什么刚刚写的前序遍历的代码，不能和中序遍历通用呢，因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。

那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。

那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

动画如下：

中序遍历，可以写出如下代码：

class Solution {
public:
    vector inorderTraversal(TreeNode* root) {
        vector result;
        stack st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) { // 指针来访问节点，访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左
            } else {
                cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                st.pop();
                result.push_back(cur->val);     // 中
                cur = cur->right;               // 右
            }
        }
        return result;
    }
};

后序遍历（迭代法）

再来看后序遍历，先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图：

所以后序遍历只需要前序遍历的代码稍作修改就可以了，代码如下：

class Solution {
public:
    vector postorderTraversal(TreeNode* root) {
        stack st;
        vector result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            result.push_back(node->val);
            if (node->left) st.push(node->left); // 相对于前序遍历，这更改一下入栈顺序 （空节点不入栈）
            if (node->right) st.push(node->right); // 空节点不入栈
        }
        reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了
        return result;
    }
};

总结

此时我们用迭代法写出了二叉树的前后中序遍历，大家可以看出前序和中序是完全两种代码风格，并不想递归写法那样代码稍做调整，就可以实现前后中序。

这是因为前序遍历中访问节点（遍历节点）和处理节点（将元素放进result数组中）可以同步处理，但是中序就无法做到同步！

上面这句话，可能一些同学不太理解，建议自己亲手用迭代法，先写出来前序，再试试能不能写出中序，就能理解了。

那么问题又来了，难道二叉树前后中序遍历的迭代法实现，就不能风格统一么（即前序遍历改变代码顺序就可以实现中序和后序）？

当然可以，这种写法，还不是很好理解，我们将在下一篇文章里重点讲解，敬请期待！

其他语言版本

Java：

// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
class Solution {
    public List preorderTraversal(TreeNode root) {
        List result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return result;
    }
}

// 中序遍历顺序: 左-中-右 入栈顺序： 左-右
class Solution {
    public List inorderTraversal(TreeNode root) {
        List result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
           if (cur != null){
               stack.push(cur);
               cur = cur.left;
           }else{
               cur = stack.pop();
               result.add(cur.val);
               cur = cur.right;
           }
        }
        return result;
    }
}

// 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
class Solution {
    public List postorderTraversal(TreeNode root) {
        List result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
}

Python：

# 前序遍历-迭代-LC144_二叉树的前序遍历
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # 根结点为空则返回空列表
        if not root:
            return []
        stack = [root]
        result = []
        while stack:
            node = stack.pop()
            # 中结点先处理
            result.append(node.val)
            # 右孩子先入栈
            if node.right:
                stack.append(node.right)
            # 左孩子后入栈
            if node.left:
                stack.append(node.left)
        return result
        
# 中序遍历-迭代-LC94_二叉树的中序遍历
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        stack = []  # 不能提前将root结点加入stack中
        result = []
        cur = root
        while cur or stack:
            # 先迭代访问最底层的左子树结点
            if cur:     
                stack.append(cur)
                cur = cur.left  
            # 到达最左结点后处理栈顶结点    
            else:  
                cur = stack.pop()
                result.append(cur.val)
                # 取栈顶元素右结点
                cur = cur.right 
        return result
        
# 后序遍历-迭代-LC145_二叉树的后序遍历
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        stack = [root]
        result = []
        while stack:
            node = stack.pop()
            # 中结点先处理
            result.append(node.val)
            # 左孩子先入栈
            if node.left:
                stack.append(node.left)
            # 右孩子后入栈
            if node.right:
                stack.append(node.right)
        # 将最终的数组翻转
        return result[::-1]

编辑：黄飞

阅读全文

二叉树(12209) 二叉树(12209)
递归(8974) 递归(8974)
python(83364) python(83364)

为什么可以用迭代法来实现二叉树的前后中序遍历呢

我们在栈与队列：匹配问题都是栈的强项中提到了，递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

2022-07-19 11:50:17

811

2016大疆笔试题与总结（编程类）

总体来说，大疆的题目不算太难。尤其是编程题，思路很清晰，不涉及到太复杂的算法。只有第三题可能涉及到递归操作(软肋)。其中第二题有关完全二叉树的操作，只需要知道完全二叉树的四个重要性质就对了,借助数学

2017-11-21 15:28:38

二叉查找树（GIF动图讲解）

二叉查找树（Binary Search Tree），也称二叉搜索树，是指一棵空树或者具有下列性质的二叉树： ·任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；·任意节点的右子树不空

2017-07-29 15:24:17

二叉树删除算法

二叉树的删除操作主要是寻找替代点来进行替换操作。方法：先右转，再一直左转，直到左连接为空的那个点。然后，摘取出来，完成链接指向操作。public void deletmin(void){ root

2016-12-30 20:55:22

用C语言构建一个二叉树失败

; ,tree.leftnode->data);这三个输出都是乱码，我不知道二叉树的建立过程中问题在哪里，我应该在每个节点都分配了内存，不过结果好像有问题}

2020-03-24 03:47:54

迭代法求值

X（n+1)=a/(b+Xn)，其中a，b为正的常数迭代的终止条件为|Xn+1-Xn|

2016-06-06 02:02:53

C语言单片机栈、堆、堆栈的区别（仅供参考）相关资料分享

堆区的；栈区（STACK）：存放临时/局部变量。1.数据结构的堆和栈1）栈：只能在一端进行插入和删除的操作的线性表。2）堆：堆的物理存储结构是一维数组，逻辑存储结构是完全二叉树...

2021-07-01 07:31:40

Java编程求二叉树的镜像两种方法介绍

给出一棵二叉树，求它的镜像，如下图：右边是二叉树是左边二叉树的镜像。仔细分析这两棵树的特点，看看能不能总结出求镜像的步骤。这两棵树的根节点相同，但他们的左右两个子节点交换了位置。因此我们不妨先在树中

2020-12-16 16:25:30

MySQL数据库索引的底层是怎么实现的

的，存储的书序也是无序的，因此hash表数据结构无法完成范围查询，比如>,<，like这些情况。显然是不满足条件的。平衡二叉树：平衡二叉树是左右子树高度差绝对值不超过1，而且

2022-07-28 15:30:46

matlab牛顿迭代法全解

非线性方程（或方程组）问题可以描述为求 x 使得f(x) = 0。在求解非线性方程的方法中，牛顿迭代法是求非线性方程（非线性方程组）数值解的一种重要的方法。牛顿是微积分创立者之一，微积分

2012-03-08 16:22:24

static的作用是什么

，是什么区别？什么是平衡二叉树？堆栈溢出一般是由什么原因导致的？冒泡排序算法的时间复杂度是什么？什么函数不能声明为虚函数？队列和栈有什么区别？不能做switch()的参数类型局部变量能否和全局变量重名？如...

2021-10-27 06:22:37

【案例分享】经典的压缩算法Huffman算法

Priority为2+2=4的结点，然后再放回Priority Queue中 :继续我们的算法（我们可以看到，这是一种自底向上的建树的过程）：最终我们会得到下面这样一棵二叉树：此时，我们把这个树的左支

2019-07-17 04:30:00

什么是“红黑树”看了就知道

今天我们要说的红黑树就是就是一棵非严格均衡的二叉树，均衡二叉树又是在二叉搜索树的基础上增加了自动维持平衡的性质，插入、搜索、删除的效率都比较高。红黑树也是实现 TreeMap 存储结构的基石。

2020-10-27 17:00:24

华为笔试题大全分享

描述实时系统的基本特性在特定时间内完成特定的任务，实时性与可靠性。4.全局变量和局部变量在内存中是否有区别？如果有，是什么区别？全局变量储存在静态数据库，局部变量在堆栈。5.什么是平衡二叉树？左右子树

2020-07-01 18:26:07

华为笔试题大全（史上最齐全）

储存在静态数据库，局部变量在堆栈。5.什么是平衡二叉树？左右子树都是平衡二叉树 且左右子树的深度差值的绝对值不大于1。6.堆栈溢出一般是由什么原因导致的？没有回收垃圾资源。7.什么函数不能声明为虚函数

2020-06-23 08:49:18

参数寻优的迭代法的基本原理是什么？伺服控制系统常用参数寻优算法是什么？

参数寻优的迭代法的基本原理是什么？伺服控制系统常用参数寻优算法是什么？

2021-10-13 06:38:28

基于牛顿迭代法的FPGA定点小数计算

倒数运算分为这两个步骤则需要更多的时间开销和空间开销。而采用常规的浮点运算单元（FPU）来求解的话，同样需要很长的计算时间。本文介绍一种基于牛顿迭代法（又称Newton-Raphson算法）的平方根

2019-07-18 07:33:50

如何用labview编写最小二乘圆法

怎么用labview编写最小二乘圆法呢？

2019-04-10 16:47:34

嵌入式基本数据结构相关资料分享

F和Q分别指向单链表两个元素的指针，那么F所指元素是Q所指元素的后继条件是？4.入栈和出栈操作最后的序列，二叉树的中序，前序，后序遍历5.哪些事件会导致进程的创建:用户登录，作业调度，提供服务，应用请求6.现代计算机按存储结构方式可划分为复杂指令集计算机和精简指令集计算机贴一张32位系统下类型字节表

2021-12-22 06:48:52

收藏 | 程序员面试，你必须知道的8大数据结构

黑树2-3树其中，二叉树和二叉搜索树是最常用的树。面试中关于树结构的常见问题：求二叉树的高度在二叉搜索树中查找第k个最大值查找与根节点距离k的节点在二叉树中查找给定节点的祖先节点字典树（Trie）字典

2018-09-30 09:35:07

数据结构试题库，含答案

的左子树，然后访问该节点，最后访问节点的右子树，这种遍历称为()。A. 中序遍历 B. 后序遍历 C. 先序遍历 D. 层次遍历17. 一个具有767个节点的完全二叉树，其叶子节点个数为()。18.

2019-03-07 16:19:44

计算机二级二叉树的问题

各位大神，本人马上要考计算机二级了，那个二叉树老是弄不明白，比如一个题目，一棵二叉树共有25个节点，其中五个叶子节点，则度为1的节点数为？

2012-09-04 09:45:06

采用高级语言开发FPGA的探索

，本次实验中二叉树的第STEP步的所有节点期货价格计算由CPU和FPGA共同完成。开发环境如下：本次课题验证了二叉树期权定价算法中步数分别为32,64,128,256,512和1024时，CPU计算结果

2017-09-25 10:06:29

问题:matlab实现牛顿迭代法求解非线性方程

"matlab实现牛顿迭代法求解非线性方程"。通过试着运行作者的matlab code，产生了如下一些疑问，请各位老师帮忙解答，不胜感谢。clearclcsyms x1 x2 x3

2014-07-05 02:53:54

迭代法迭代阵谱半径新上界

引用双严格对角占优的概念，针对线性方程组bAx=在求数值解时常用的迭代方法，给出了Jacobi和Gauss-Seidel迭代法迭代阵谱半径的新上界，该新上界优于严格对角占优矩阵条件下得到

2008-11-18 00:07:26

二叉树算法在单总线技术中的应用

介绍了单总线技术和二叉树算法。单总线技术可以将地址线、数据线和控制线合成一根线，并允许在这根线上挂接多个单总线器件。提出了用二叉树算法搜索单总线器件注册码，并

2009-03-16 09:38:12

基于二叉树分解的自适应防碰撞算法

该文提出了一种基于二叉树分解的自适应防碰撞算法。新算法利用标签EPC 的唯一性，通过时隙分配估计标签的分布情况，对发生碰撞的时隙进行二叉树搜索，从而将一个庞大且复杂

2009-11-17 14:09:28

基于Hash和二叉树的路由表查找算法

基于Hash和二叉树的路由表查找算法 :提出了一种基于Hash和二又树的路由表查找算法，这一算法可以满足()C-768的转发要求，支持超过10万条前缀的大规模路由表，并且

2010-02-22 17:06:15

用迭代法求指纹图像中的阀值

摘要：给出使用直方图方法求阀值的例子；结合直方图方法提出用于计算最优阀值的迭代法，该方法是基于256级的指纹灰度图像计算；最后给出迭代法中初值的选择

2006-03-24 12:47:53

1010

在GPU上实现Jacobi迭代法的分析与设计

随着GPU技术的快速发展，GPU的浮点运算能力飞速提升。将GPU浮点处理能力用于非图形计算领域正成为高性能计算领域的热点研究问题。Jacobi迭代法是科学计算中常用的计算方法。在分析

2012-06-06 16:44:24

数据结构：二叉树的中序遍历(1)#结构数据

数据结构

学习硬声知识发布于 2022-12-18 00:58:17

数据结构：二叉树的中序遍历(2)#结构数据

数据结构

学习硬声知识发布于 2022-12-18 00:58:39

数据结构：二叉树的先序遍历(1)#结构数据

数据结构

学习硬声知识发布于 2022-12-18 00:59:02

数据结构：二叉树的先序遍历(2)#结构数据

数据结构

学习硬声知识发布于 2022-12-18 00:59:26

基于二叉树的时序电路测试序列设计

为了实现时序电路状态验证和故障检测，需要事先设计一个输入测试序列。基于二叉树节点和树枝的特性，建立时序电路状态二叉树，按照电路二叉树节点(状态)与树枝(输入)的层次逻辑

2012-07-12 13:57:40

数据结构与算法：4.1.5 二叉树的迭代遍历-5-层序实现(1)#结构数据

数据结构

学习硬声知识发布于 2022-12-18 11:51:25

数据结构与算法：4.1.5 二叉树的迭代遍历-5-层序实现(2)#结构数据

数据结构

学习硬声知识发布于 2022-12-18 11:51:48

C++数据结构 -二叉树先序遍历_中序遍历_后序遍历

C++

电路设计发布于 2023-01-05 15:44:22

[4.4.1]--4.4.1二叉树的遍历

算法数据结构

jf_60701476发布于 2023-01-24 21:00:47

[6.2.1]--二叉树与树的遍历

数据结构

jf_75936199发布于 2023-03-15 02:03:28

[6.5.1]--二叉树的遍历

数据结构

jf_75936199发布于 2023-03-15 02:51:22

[3.3.1]--3.3二叉树的遍历（一）

数据结构数据结构与算法

jf_75936199发布于 2023-03-15 10:42:54

[3.4.1]--3.4二叉树的遍历（二）

数据结构数据结构与算法

jf_75936199发布于 2023-03-15 10:43:35

高斯-牛顿迭代法简介

高斯牛顿迭代法简介，包括高斯牛顿迭代法推演及及结论

2016-01-08 16:21:26

二叉树的遍历(1)#数据结构

数据结构

未来加油dz发布于 2023-07-18 15:49:33

二叉排序树（2）(2)#数据结构

数据函数二叉树

未来加油dz发布于 2023-09-05 09:04:56

二叉树和二叉树的性质(1)#数据结构

数据函数二叉树

未来加油dz发布于 2023-09-05 09:06:44

二叉树和二叉树的性质(2)#数据结构

数据函数二叉树

未来加油dz发布于 2023-09-05 09:08:32

二叉树和二叉树的性质(3)#数据结构

数据函数二叉树

未来加油dz发布于 2023-09-05 09:09:51

平衡二叉树(1)#数据结构

数据函数二叉树

未来加油dz发布于 2023-09-05 09:42:30

平衡二叉树(2)#数据结构

数据函数二叉树

未来加油dz发布于 2023-09-05 09:43:54

平衡二叉树(3)#数据结构

数据函数二叉树

未来加油dz发布于 2023-09-05 09:45:06

二叉树的遍历(1)#数据结构

数据函数代码

未来加油dz发布于 2023-09-06 08:43:59

二叉树的遍历(2)#数据结构

数据函数代码

未来加油dz发布于 2023-09-06 08:45:15

基于类二叉树的圆锥型UWSNs的研究_陈军

基于类二叉树的圆锥型UWSNs的研究_陈军

2017-03-19 19:28:03

二叉树的前序遍历、中序遍历、后续遍历的非递归实现

前序遍历：先访问该节点，然后访问该节点的左子树和右子树；中序遍历：先访问该节点的左子树，然后访问该节点，再访问该节点的右子树；后序遍历：想访问该节点的左子树和右子树，然后访问该节点。

2017-11-27 11:24:24

1004

二叉树层次遍历算法的验证

实现二叉树的层次遍历算法，并对用”A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”创建的二叉树进行测试。

2017-11-28 01:05:46

1881

基于二叉树的算术编码二值化方法

在算术编码研究中，待编码的语法元素需要采用何种二值化方法以及二值化后每个比特的概率模型选择是算术编码算法设计必须面对的问题．提出了一种基于二叉树的熵编码二值化方法．该方法首先获得语法元素的统计概率

2018-01-03 16:53:17

熵的二叉树多类支持向量机的漏洞分类

为了有效提高漏洞分类的准确性，针对基于二叉树多类支持向量机分类算法的分类复杂性和分类结果依赖二叉树的结构等缺点，提出了一种基于熵的二又树多类支持向量机的漏洞分类算法。根据定义最小超球体进行漏洞

2018-01-25 10:40:38

关于二叉树一些数据结构和算法相关的题目

最近总结了一些数据结构和算法相关的题目，这是第一篇文章，关于二叉树的。

2018-02-07 13:57:10

2985

4中二叉树的遍历方式介绍

对于一种数据结构而言，遍历是常见操作。二叉树是一种基本的数据结构，是一种每个节点的儿子数目都不多于2的树。

2018-04-27 17:23:50

4511

二叉树，一种基础的数据结构类型

然后我们再定义一棵深度也为 3 的二叉树，该二叉树的 n 个结点（n≤7），当从 1 到 n 的每个结点都与上图中的编号结点一一对应时，这二叉树就称为完全二叉树。

2019-04-13 10:48:26

3949

详解电源二叉树到底是什么

作为数据结构的基础，树分很多种，像 AVL 树、红黑树、二叉搜索树....今天我想分享的是关于二叉树，一种基础的数据结构类型。今天从实例入手，给大家介绍一个电源二叉树的分析。

2019-06-06 15:05:46

9235

PCB板设计的电源二叉树分析详细资料说明

本文档的主要内容详细介绍的是PCB板设计的电源二叉树分析详细资料说明。

2019-07-29 08:00:00

C语言二叉树代码免费下载

本文档的主要内容详细介绍的是C语言二叉树代码免费下载。

2019-08-27 08:00:00

面试算法之重建二叉树

那么问题来了，只知道前序遍历能不能反推二叉树呢？我们就试一下，比如题目中所述，{1,2,4,7,3,5,6,8}，根据前序遍历，根、左、右，1 肯定是根节点，那么一下2,4,7

2019-11-27 15:59:39

2321

面试二叉树看这11个就够了

根据前、中序遍历的特点，（根左右、左根右），先根据前序遍历确定根节点，然后在中序遍历知道该根节点的左右树的数量，反推出前序遍历中左子树的结点有哪些。根据该思路进行递归即可完成二叉树的重建。

2019-11-27 16:25:06

3151

红黑树（Red Black Tree）是一种自平衡的二叉搜索树

平衡（Balance）：就是当结点数量固定时，左右子树的高度越接近，这棵二叉树越平衡（高度越低）。而最理想的平衡就是完全二叉树/满二叉树，高度最小的二叉树。

2020-07-01 15:05:40

4598

二叉树操作的相关知识和代码详解

见的二叉树操作作个总结：前序遍历，中序遍历，后序遍历；层次遍历；求树的结点数；求树的叶子数；求树的深度；求二叉树第k层的结点个数；判断两棵二叉树是否结构相同；求二叉树的镜像；求两个结点的最低公共祖先结点；求任

2020-12-12 11:04:44

1770

二叉树的前序遍历非递归实现

通过下面这个动画复习一下二叉树的前序遍历。迭代遍历我们试想一下，之前我们借助队列帮我们实现二叉树的层序遍历，那么可不可以，也借助数据结构，帮助我们实现二叉树的前序遍历。假设我们的二叉树为［1，2，3］。我们需

2021-05-28 13:59:07

1651

二叉树的所有路径介绍

以为只用了递归，其实还用了回溯 257. 二叉树的所有路径题目地址：https://leetcode-cn.com/problems/binary-tree-paths/ 给定一个二叉树，返回所有

2021-08-13 17:51:51

2931

C语言编程中如何求出二叉树后序遍历

题目已知二叉树前序为 ABDFGCEH 后序序列为 BFDGACEH ，要求输出后序遍历为 FGDBHECA 大体思路又先序得出根，先序的根后为左树一部分，我们再在中序序列里找到先序的根，此处

2021-08-23 11:04:52

3491

如何才能够翻转二叉树

有所收获！ 226.翻转二叉树题目地址：https://leetcode-cn.com/problems/invert-binary-tree/ 翻转一棵二叉树。这道题目背后有一个让程序员心酸的故事

2021-09-01 11:45:31

1515

C++基础语法中的二叉树详解

本期是C++基础语法分享的第十四节，今天给大家来梳理一下树！ 二叉树 BinaryTree.cpp： #include 《stdio.h》#include 《stdlib.h》 #define

2021-09-29 18:02:52

1874

算法学习中如何打印二叉树节点

大家好，我是吴师兄，直接开始今天的算法学习，冲冲冲。一、题目描述从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。例如: 给定二叉树: [3,9,20,null,null

2021-10-22 09:37:00

1390

二叉排序树AVL如何实现动态平衡

熟悉的二叉树种类有二叉搜索(排序、查找)树、二叉平衡树、伸展树、红黑树等等。而熟悉的多叉树像B树、字典树都是经典多叉树。普通的二叉树，我们研究其遍历方式，因为其没啥规则约束查找和插入都很随意所以很少有研究价值。但是二叉树结构上很有

2021-10-28 17:02:26

1445

数据结构与算法分析中的二叉树与堆有关知识汇总

该资料包括数据结构与算法分析中的二叉树与堆有关的一些知识

2021-11-03 09:37:26

二叉树上应该怎么求

二叉树上应该怎么求，二叉搜索树上又应该怎么求？在求众数集合的时候有一个技巧，因为题目中众数是可以有多个的，所以一般的方法需要遍历两遍才能求出众数的集合。但可以遍历一遍就可以求众数集合，使用了

2021-11-22 11:32:46

1171

C语言数据结构：什么是二叉树？

完全二叉树：完全二叉树是效率很高的数据结构。对于深度为K，有n个节点的二叉树，当且仅当每一个节点都与深度为K的满二叉树中编号从1至n的节点一一对应时，称为完全二叉树。

2022-04-21 16:20:10

1646

二叉树的最小深度

遍历顺序上依然是后序遍历（因为要比较递归返回之后的结果），但在处理中间节点的逻辑上，最大深度很容易理解，最小深度可有一个误区，如图：

2022-04-28 16:27:09

1469

判断对称二叉树要比较的是哪两个节点

对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，理解这一点就知道了其实我们要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。

2022-07-06 16:26:05

767

怎么就能构造成二叉树呢？

一直跟着公众号学算法的录友应该知道，我在二叉树：构造二叉树登场！，已经讲过，只有中序与后序和中序和前序可以确定一颗唯一的二叉树。前序和后序是不能确定唯一的二叉树的。

2022-07-14 11:20:47

972

二叉树的最大深度

精简之后的代码根本看不出是哪种遍历方式，也看不出递归三部曲的步骤，所以如果对二叉树的操作还不熟练，尽量不要直接照着精简代码来学。

2022-07-26 11:28:54

733

二叉树的统一迭代法

我们以中序遍历为例，在二叉树：听说递归能做的，栈也能做！中提到说使用栈的话，无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。

2022-08-03 11:22:59

318

二叉树按任意顺序，返回所有路径程序实现

题目：给你一个二叉树的根节点root ，按任意顺序，返回所有从根节点到叶子节点的路径。

2022-09-20 11:35:24

633

使用C语言代码实现平衡二叉树

这篇博客主要总结平衡二叉树，所以，二叉排序树知识不会提及，但是会用到。

2022-09-21 11:00:42

721

二叉树的代码实现

二叉树的主要操作有遍历，例如有先序遍历、中序遍历、后序遍历。在遍历之前，就是创建一棵二叉树，当然，还需要有删除二叉树的算法。

2023-01-18 10:41:00

868

C++构建并复制二叉树

使用C++构建一个二叉树并复制、输出。

2023-01-10 15:17:10

703

C++自定义二叉树并输出二叉树图形

使用C++构建一个二叉树并输出。

2023-01-10 16:29:36

1157

解析LeetCode第226号题目：反转二叉树

*简单讲就是把每个节点的左子树和右子树进行交换** 。显然，这需要我们能够遍历该二叉树。那么遍历二叉树就有两种经典的解法：深度优先遍历，Deep First Search，简称DFS；另一个是广度优先遍历，Breadth First Search，简称BFS。

2023-02-17 14:52:30

613

牛顿-拉夫逊迭代法原理及其实现

直接看数学公式描述如何迭代不直观，先来看动图就很容易理解牛顿迭代法为什么叫迭代法以及怎样迭代的

2023-04-17 09:04:03

1491

这么简单的二叉树算法都不会？

这个题目是leetcode的第572题，要求是这样的：给定两颗二叉树A和B，判断B是否是A的子树。

2023-08-29 11:19:41

477

python牛顿迭代法

牛顿迭代法是一种数值计算方法，用于求解方程的数值近似解。它是以英国科学家艾萨克·牛顿的名字命名的，最初由牛顿在17世纪末提出。牛顿迭代法基于一个简单的原理：一条曲线的切线近似代替这条曲线，在切线

2023-11-21 15:06:51

323

树与二叉树的定义

树型结构是一类重要的非线性数据结构，其中以树和二叉树最为常用，直观来看，树是以分支关系定义的层次结构。树型结构在客观世界中广泛存在，比如人类社会中的祖辈关系，社会机构组织等等都可以用树来形象

2023-11-24 15:57:30

430

已全部加载完成

搜索历史

用迭代法编写二叉树的前后中序遍历案例

评论