首页 > 其他分享 >二叉树的递归遍历和迭代遍历

二叉树的递归遍历和迭代遍历

时间:2024-11-08 10:42:15浏览次数:1  
标签:pre 遍历 出栈 迭代 递归 nullptr st 二叉树

递归

每次写递归,都按照这三要素来写,可以保证大家写出正确的递归算法!

确定递归函数的参数和返回值: 确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数, 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

确定终止条件: 写完了递归算法, 运行的时候,经常会遇到栈溢出的错误,就是没写终止条件或者终止条件写的不对,操作系统也是用一个栈的结构来保存每一层递归的信息,如果递归没有终止,操作系统的内存栈必然就会溢出。

确定单层递归的逻辑: 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

迭代

后序遍历的迭代写法

后序非递归遍历二叉树,先访问左子树,再访问右子树,最后访问根节点。具体步骤为:

  1. 沿根的左孩子依次入栈,直到左孩子为空
  2. 读栈顶元素
    2.1 若右孩子不为空或右孩子未被访问过,转为右孩子结点继续执行1
    2.2 否则,栈顶元素出栈并访问

为记录元素是否被访问,设立pre指针,指向上一个出栈元素。若当前执行节点p的右孩子已被访问,说明上一个出栈元素正是p的右孩子。若未被访问则pre != p->right

代码

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> ans;
        if(root == nullptr)return {};
        TreeNode* p = root;
        TreeNode* pre = nullptr; //pre指向最近出栈的结点
        while(p || !st.empty()){
            if(p != nullptr){//不能写成p->left != nullptr然后入栈左子树,应该先入栈p本身
                st.push(p);
                p = p->left;
                // pre = root; 
            }else{
                //不能直接跟if-else,此时遍历到最左子树时p是nullptr
                p = st.top(); 
                if(p->right && pre != p->right){
                    p = p->right;
                    // pre = root;  这里还没有出栈所以不能加
                }else{//出栈
                    TreeNode* tmp = st.top();
                    ans.emplace_back(tmp->val);
                    st.pop();
                    pre = tmp;
                    p = nullptr;
                }
            }
        }
        return ans;
    }
};

每次出栈访问完一个结点就相当于遍历完以该结点为根的树,所以需要将p置为null(重新取栈顶)

标签:pre,遍历,出栈,迭代,递归,nullptr,st,二叉树
From: https://www.cnblogs.com/neromegumi/p/18534641

相关文章

  • C-牛顿迭代法求根
    牛顿迭代法:牛顿迭代法(Newton'smethod)又称为牛顿-拉夫逊(拉弗森)方法(Newton-Raphsonmethod),它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。代码:#include<stdio.h>#include<math.h>intmain(){ floatqiugeng(inta,intb,intc,intd,inte); ......
  • 华为OD机试真题-数组二叉树码-2024年OD统一考试(E卷)
    最新华为OD机试考点合集:华为OD机试2024年真题题库(E卷+D卷+C卷)_华为od机试题库-CSDN博客     每一题都含有详细的解题思路和代码注释,精编c++、JAVA、Python三种语言解法。帮助每一位考生轻松、高效刷题。订阅后永久可看,发现新题及时跟新。题目描述二叉树也可以用数组来......
  • 数据结构 ——— 链式二叉树oj题:相同的树
    目录题目要求手搓两个链式二叉树代码实现 题目要求给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。手搓两个链式二叉树代码演示://数据类型typedefintBTDataType;......
  • 数据结构 ——— 计算链式二叉树第k层的节点个数
    目录链式二叉树示意图手搓一个链式二叉树计算链式二叉树第k层的节点个数 链式二叉树示意图手搓一个链式二叉树代码演示://数据类型typedefintBTDataType;//二叉树节点的结构typedefstructBinaryTreeNode{BTDataTypedata;//每个节点的数据s......
  • 代码随想录算法训练营第十八天|leetcode530.二叉搜索树的最小绝对差、leetcode501.二
    1leetcode530.二叉搜索树的最小绝对差题目链接:530.二叉搜索树的最小绝对差-力扣(LeetCode)文章链接:代码随想录视频链接:你对二叉搜索树了解的还不够!|LeetCode:98.验证二叉搜索树_哔哩哔哩_bilibili思路:定义一个极大值作为结果,然后在中序遍历过程中进行比较出结果1.1自己的......
  • 0基础学Python——类的单例模式、反射函数、记录类的创建个数、迭代器、生成器及生成
    0基础学Python——类的单例模式、反射函数、记录类的创建个数、迭代器、生成器及生成器练习类的单例模式定义代码演示反射函数代码演示记录类的创建个数迭代器定义特点生成器定义特点写法生成器练习生成器生成1-无穷的数字生成器生成无穷个素数类的单例模式定义......
  • 0基础学Python——面向对象-可迭代、面向对象-迭代器、call方法、call方法实现装饰器
    0基础学Python——面向对象-可迭代、面向对象-迭代器、call方法、call方法实现装饰器、计算函数运行时间面向对象--可迭代实现方法面向对象--迭代器实现方法call方法作用call方法实现装饰器代码演示计算函数运行时间代码演示面向对象–可迭代把对象看做容器,存储......
  • 数据结构树与二叉树
    语雀链接:https://www.yuque.com/g/wushi-ls7km/ga9rkw/qw8kwzxigbx61kxy/collaborator/join?token=2vdSjDBgJyJb0VSL&source=doc_collaborator#《树与二叉树》......
  • 实验4:二叉树的基本操作
    c++解释:new相当于malloc()函数,其他没有区别!点击查看代码#include<iostream>usingnamespacestd;structtree{ intdata; tree*light,*ture;};intjie,shen,maxx;//创建tree*chu(){ tree*head; head=newtree; cout<<"请输入数值:\n"; cin>&g......
  • bfs(宽度搜索遍历)
    当边权为1时候,用bfs解决最短路问题题目:走迷宫给定一个 n×m的二维整数数组,用来表示一个迷宫,数组中只包含 0或 1,其中 0 表示可以走的路,1 表示不可通过的墙壁。最初,有一个人位于左上角 (1,1) 处,已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问,该......