【LeetCode】144. 二叉树的前序遍历、94. 二叉树的中序遍历、145. 二叉树的后序遍历

简介: 144. 二叉树的前序遍历144. 二叉树的前序遍历题目:

作者:小卢

专栏:《Leetcode》

喜欢的话:世间因为少年的挺身而出,而更加瑰丽。                                  ——《人民日报》


144. 二叉树的前序遍历

144. 二叉树的前序遍历

题目:

给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

示例:

思路:

我们可以将二叉树一直向走到底,这样就会有一条道最左的路径,我们将其称为左子路,我们可以将二叉树分为左子路和左子路节点的右子树等等

我们利用一个栈来存储左子路,如果到底就出栈顶,然后遍历该栈顶的右子树以此循环

代码:

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*>st;
        vector<int>v;
        TreeNode*cur=root;
        while(cur||!st.empty())
        {
            while(cur)
            {
                st.push(cur);
                v.push_back(cur->val);
                cur=cur->left;
            }
            TreeNode*top=st.top();
            st.pop();
            cur=top->right;
        }
        return v;
    }
};

94. 二叉树的中序遍历

94. 二叉树的中序遍历

题目:

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

示例:

代码:

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*>st;
        vector<int>v;
        TreeNode*cur=root;
        while(cur||!st.empty())
        {
            while(cur)
            {
                st.push(cur);
                cur=cur->left;
            }
                TreeNode*top=st.top();
                st.pop();
                v.push_back(top->val);
                    cur=top->right;
        }
        return v;
    }
};

145. 二叉树的后序遍历

145. 二叉树的后序遍历

题目:

给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历

示例:

代码:

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*>st;
        vector<int>v;
        TreeNode*cur=root;
        TreeNode*prev=nullptr;
        while(cur||!st.empty())
        {
            //左子路
            while(cur)
            {
                st.push(cur);
                cur=cur->left;
            }
            //从栈里面取到左子路的节点
            TreeNode*top=st.top();
            //这里右不存在或者右子树已经遍历了,才可以
            //prev记录上一个节点,如果prev是top的父亲,就说明右子树已经遍历了
            if(top->right==nullptr||top->right==prev)
            {
                v.push_back(top->val);
                st.pop();
                prev=top;
            }
            else
            {
                cur=top->right;
            }
        }
            return v;
    }
};


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