• LeetCode 145. 二叉树的后序遍历(Binary Tree Postorder Traversal)


    题目描述

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

    示例:

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

    进阶: 递归算法很简单,你可以通过迭代算法完成吗?

    解题思路

    后序遍历的顺序是左孩子->右孩子->父节点,对于每个遍历到的节点,执行如下操作:

    1. 首先对该节点不断沿左孩子方向向下遍历并入栈,直到左孩子为空
    2. 取出栈顶节点,此时该节点为树的最左下节点,若其右孩子不为空,则回到步骤1;若为空说明其为叶子节点,将其值输出到结果中,并记录pre为当前节点
    3. 在步骤2判断右孩子是否为空时,同时判断当前节点右孩子是否已被输出,如果pre是其右孩子,说明当前节点的所有子节点已访问过,所以不必再向下遍历,直接输出即可

    代码

     1 /**
     2  * Definition for a binary tree node.
     3  * struct TreeNode {
     4  *     int val;
     5  *     TreeNode *left;
     6  *     TreeNode *right;
     7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     8  * };
     9  */
    10 class Solution {
    11 public:
    12     vector<int> postorderTraversal(TreeNode* root) {
    13         vector<int> res;
    14         TreeNode* node = root, *pre = NULL;
    15         stack<TreeNode*> s;
    16         while(node || s.size()){
    17             while(node){
    18                 s.push(node);
    19                 node = node->left;
    20             }
    21             node = s.top();
    22             if(node->right && node->right != pre)
    23                 node = node->right;
    24             else{
    25                 res.push_back(node->val);
    26                 s.pop();
    27                 pre = node;
    28                 node = NULL;
    29             }
    30         }
    31         return res;
    32     }
    33 };
  • 相关阅读:
    进程间通信小结
    菜鸡和菜猫进行了一场Py交易
    菜鸡开始接触一些基本的算法逆向了
    菜鸡学逆向学得头皮发麻,终于它拿到了一段源代码
    静态分析-Windows找密码
    逆向-完成地址随机化关闭
    QSortFilterProxyModel 的过滤 排序
    linux命令2
    linux 命令1
    error c2059 c3905 c2148 c2238
  • 原文地址:https://www.cnblogs.com/wmx24/p/9494486.html
一二三 - 开发者的网上家园