首页 > 其他分享 >非递归形式遍历二叉树

非递归形式遍历二叉树

时间:2024-01-15 12:22:20浏览次数:32  
标签:遍历 TreeNode 递归 stk 二叉树 push root 节点

最简单的就是前序遍历,每次将栈顶元素插入数组中。
但要注意由于栈的性质,先push右节点再push左节点。

点击查看代码
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
vector<int>v;
stack<TreeNode*>stk;
if(root!=NULL){stk.push(root);}
while(!stk.empty()){
    TreeNode*p=stk.top();
   v.push_back(p->val);
    stk.pop();
    if(p->right){stk.push(p->right);}
    if(p->left){stk.push(p->left);}
   
}
return v;
    }
};
后序遍历,只要改动这一点,先push左节点再push右节点,这时候的顺序就是根右左,将数组reverse就是左右根了。 稍微复杂的就是中序遍历,因为它访问顺序与数组插入顺序不同,要换一种方法。 循环终止条件就是遍历指针为空同时栈为空, 遍历指针为空,就不断向栈中加入左子树,不为空就向数组插入堆顶元素,然后遍历指针换成右子树。
点击查看代码
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
vector<int>v;
stack<TreeNode*>stk;
TreeNode*p=root;
while(p!=NULL||!stk.empty()){
    if(p!=NULL){
        stk.push(p);
        p=p->left;
    }
    else{
        p=stk.top();
        v.push_back(p->val);
        stk.pop();
        p=p->right;
    }
}
return v;
    }
};

标签:遍历,TreeNode,递归,stk,二叉树,push,root,节点
From: https://www.cnblogs.com/yun-che/p/17965115

相关文章

  • C++U3-第09课-递归函数的应用
    学习目标 斐波那契数列例题  我们需要求出斐波那契第n项的值是多少【思路分析】我们用递归的方式去求解,当第一项和第二项返回1,否则返回前两项的和当前为第一项和第二项返回1当前不为第一项和第二项返回前两项的和定义n并把n输入,带入到递归求解【参考代......
  • 一套模板搞定二叉树算法题--二叉树算法讲解002
    1、二叉树的递归递归:2、二叉树遍历之DFS深度优先遍历2.1、遍历的概念每个节点都要恰好被访问一次,本质上是二叉树的线性化。一个树形的结构,线性化为一个数组之类的"串"的结构。2.2、DFS深度优先遍历示例二叉树原型图:2.2.1、前序遍历前序遍历执行顺序:根节点--对左子......
  • #yyds干货盘点# LeetCode程序员面试金典:二叉树的直径
    题目给你一棵二叉树的根节点,返回该树的直径。二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点root。两节点之间路径的长度由它们之间边数表示。 示例1:输入:root=[1,2,3,4,5]输出:3解释:3,取路径[4,2,1,3]或[5,2,1,......
  • 代码随想录 day18 找树左下角的值 路径总和 从中序与后序遍历序列构造二叉树
    找树左下角的值最简单就是想到层序遍历之后取第一个位置元素就是了递归的话需要先判断哪里最深的节点至于最左保持中左右的遍历顺序第一次得到最大深度处就是最左的路径总和有点像查找子树路径所以递归回溯是比较好的选择在求路径的适合,targetSum-node->val是否为......
  • 代码随想录 day17 平衡二叉树 二叉树的所有路径 左叶子之和
    平衡二叉树之前一直写迭代代码没有怎么写递归正好这题不是很好写迭代练习一下递归这题递归逻辑相对简单左右子树高度差判断是不是大于一可以直接返回结果不大于一就高度max(l,r)+1二叉树的所有路径关键要点这题适合先序遍历回溯过程和递归过程是一起写的进来几次......
  • 递归实现二分
    publicclassBinarySearch{privateint[]array;/***递归实现二分查找*@paramtarget*@return*/publicintsearchRecursion(inttarget){if(array!=null){returnsearchRecursion(target,0,array.lengt......
  • Java递归函数计算递归次数出错
    背景:构造组织架构树时,使用了递归填充子节点,为防止环状的错误数据导致递归无法结束,记录递归的次数,超过一定数量后终止递归问题:用户记录递归次数的变量在节点跳转的时候被重新赋值,无法正确记录 publicDepartgenDepartTreeFromRoot()throwsException{Departroot=De......
  • JOSN字符串字段遍历(json-path)
    官网https://github.com/json-path/JsonPath依赖<dependency><groupId>com.jayway.jsonpath</groupId><artifactId>json-path</artifactId><version>2.5.0</version></dependency>......
  • day13 代码随想录算法训练营 递归遍历
    题目:144.二叉树的前序遍历145.二叉树的后序遍历94.二叉树的中序遍历我的感悟:用helper内部函数写更好理解难点: 代码难点:代码示例:前序#Definitionforabinarytreenode.#classTreeNode:#def__init__(self,val=0,left=None,right=None):#......
  • Java反射遍历判断值是否属于枚举类Enum
    首先,是一个枚举类:publicenumAuditState{TO_BE_AUDIT(0,"待审核"),AUDITED(1,"已审核");privateStringmessage;privateIntegercode;AuditState(Integercode,Stringmessage){this.message......