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

我不是女神ヾ 2024-03-16 13:51 69阅读 0赞

>  作者：小卢
> 
> 专栏：《Leetcode》
> 
> 喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
> 
> ![7d63d497b5114103b3dd7633a1ba4731.jpeg][]
> 
> --------------------

## 144. 二叉树的前序遍历 ##

[144. 二叉树的前序遍历][144.]

题目：

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

示例：

![a2ad3d0e7b73408fbb80a21b5e4cfa84.png][]

思路：

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

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

代码：

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. 二叉树的中序遍历][94.]

题目：

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

示例：

![14e17751cc274b0abf6b06dbbf3f64bd.png][]

代码：

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. 二叉树的后序遍历][145.]

题目：

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

示例：

![34b9ed29ba8a4288915965d3d8151d9d.png][] 代码：

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;
            
        }
    };

[7d63d497b5114103b3dd7633a1ba4731.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/17855fe87f6448dfa4a871eb93a77895.png
[144.]: https://leetcode.cn/problems/binary-tree-preorder-traversal/
[a2ad3d0e7b73408fbb80a21b5e4cfa84.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/8e2df7f7e5f64d7ba3d15010774d86f2.png
[94.]: https://leetcode.cn/problems/binary-tree-inorder-traversal/
[14e17751cc274b0abf6b06dbbf3f64bd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/04fd0d655e3b4f34b26746096ed28cd6.png
[145.]: https://leetcode.cn/problems/binary-tree-postorder-traversal/
[34b9ed29ba8a4288915965d3d8151d9d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/cb879af2b97f488491e546e266e29695.png