leetcode94二叉树的中序遍历(迭代做法)

简介: leetcode94二叉树的中序遍历(迭代做法)

题目描述:

给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。

示例 1:

输入:root = [1,null,2,3]
输出:[1,3,2]

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [1]
输出:[1]

提示:

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

题解思路:

二叉树中序遍历的迭代方法,利用指针来访问节点,一直往左节点访问,直到左节点为空则停止,然后是根,右节点

  • 利用栈来保存访问的节点

代码:

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        vector<int> result;
        TreeNode * temp = root; 
        while(temp || !s.empty()){
            if(temp){  // 一直访问存在的左节点
                s.push(temp);  //放入左节点
                temp = temp->left;
            }else{
                temp = s.top();  //相当于null的父节点,此null是父节点的左节点
                s.pop();
                result.push_back(temp->val);  //这一步就相当于访问根节点
                temp = temp->right;
            }
        }
        return result;
    }
};


相关文章
|
1月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
18天前
|
算法
刷算法Leetcode---9(二叉树篇Ⅲ)
刷算法Leetcode---9(二叉树篇Ⅲ)
15 3
|
1月前
|
算法
二刷力扣--二叉树(3)
二刷力扣--二叉树(3)
|
1月前
二刷力扣--二叉树(2)
二刷力扣--二叉树(2)
|
1月前
二刷力扣--二叉树(1)基础、遍历
二刷力扣--二叉树(1)基础、遍历
|
1月前
|
存储 算法 数据可视化
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)
|
1月前
|
算法 数据可视化 数据挖掘
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )
|
1月前
|
存储 缓存 算法
LeetCode力扣题目111:多种算法对比实现二叉树的最小深度
LeetCode力扣题目111:多种算法对比实现二叉树的最小深度
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题