LeetCode题目：二叉树的后序遍历

分手后的思念是犯贱 2021-12-14 06:57 356阅读 0赞

## 二叉树的后序遍历 ##

给定一个二叉树，返回它的 后序 遍历。

**示例:**

输入: [1,null,2,3]  
       1
        \
         2
        /
       3 
    
    输出: [3,2,1]

后序遍历比较复杂，但有种非常简单的方法:

把前序遍历反转  
    	 如前序： root->left->right
    	 修改前序： root->right->left
    	 反转前序得到后序遍历：left->right->root

class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
            vector<int> res;
            if(root == NULL)
                return res;
            vector<TreeNode*> S;
            TreeNode* p = root;
            while(p!= NULL || !S.empty())
            {
                if( p!= NULL)
                {
                    S.push_back(p);
                    res.push_back(p->val);
                    p = p->right;
                }
                else
                {
                    p = S.back();
                    S.pop_back();
                    p = p->left;
                }
            }
            reverse(res.begin(), res.end());  
            return res;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，356人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode二叉树系列——145.二叉树的后序遍历

一、题目描述： [144. 二叉树的前序遍历][144.] 给你二叉树的根节点 `root` ，返回它节点值的后序遍历。、![c4df3bd2adbb4b1393

Bertha 。/ 2023年09月28日 17:31/ 0 赞/ 90 阅读

相关 leetcode 145 二叉树的后序遍历

给定一个二叉树，返回它的后序遍历。示例: 输入: \[1,null,2,3\] 1 2 / 3 输出: \[3,2,1\] /

我就是我/ 2023年06月17日 05:52/ 0 赞/ 1 阅读

相关二叉树的后序遍历

二叉树文章系列： 1. [二叉树的前序遍历][Link 1] 2. [二叉树的中序遍历][Link 2] 3. [二叉树的后序遍历][Link 3] 4. [二叉树的

约定不等于承诺〃/ 2022年10月22日 04:08/ 0 赞/ 156 阅读

相关二叉树先序遍历中序遍历建立二叉树然后后序遍历

题目描述二叉树的前序、中序、后序遍历的定义：前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；中序遍历：对任一子树，先遍历其左

男娘i/ 2022年06月01日 07:24/ 0 赞/ 252 阅读

相关 LeetCode题目：二叉树的后序遍历

二叉树的后序遍历给定一个二叉树，返回它的后序遍历。示例: 输入: [1,null,2,3] 1 \

分手后的思念是犯贱/ 2021年12月14日 06:57/ 0 赞/ 357 阅读

相关 LeetCode题目：二叉树的前序遍历

二叉树的前序遍历给定一个二叉树，返回它的前序遍历。示例: 输入: [1,null,2,3] 1 \

阳光穿透心脏的1/2处/ 2021年12月14日 06:49/ 0 赞/ 198 阅读

相关 LeetCode题目：二叉树的中序遍历

二叉树的中序遍历给定一个二叉树，返回它的中序遍历。示例: 输入: [1,null,2,3] 1 \ 2

- 日理万妓/ 2021年12月14日 06:47/ 0 赞/ 241 阅读

相关题目24 二叉搜索树的后序遍历

/ // 6. 题目24 二叉搜索树的后序遍历 // 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果！！！ /\ 8 / \\ 6 10

深碍√TFBOYSˉ_/ 2021年11月02日 01:02/ 0 赞/ 205 阅读

相关二叉树(先序遍历，中序遍历，后序遍历)

二叉树定义每个节点的子节点数(度)不能大于2 先序遍历定义：从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。

悠悠/ 2021年10月01日 09:18/ 0 赞/ 462 阅读

相关题目1078：二叉树遍历（由前序遍历中序遍历得到后序遍历）

[题目链接：http://ac.jobdu.com/problem.php?pid=1078][http_ac.jobdu.com_problem.php_pid_1078]

痛定思痛。/ 2021年09月29日 13:36/ 0 赞/ 347 阅读