LeetCode145—Binary Tree Postorder Traversal

叁歲伎倆 2022-07-16 04:22 138阅读 0赞

## 原题 ##

[原题链接][Link 1]

> Given a binary tree, return the postorder traversal of its nodes’ values.
> 
> For example:  
> Given binary tree \{1,\#,2,3\},  
> 1  
> \\  
> 2  
> /  
> 3  
> return \[3,2,1\].
> 
> Note: Recursive solution is trivial, could you do it iteratively?

## 分析 ##

后序遍历的迭代写法，参见：[二叉树遍历][Link 2]

//递归算法略
    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
            vector<int>res;
            if(!root)
            {
                return res;
            }
            TreeNode *cur;
            TreeNode *pre=NULL;
            stack<TreeNode*>s;
            s.push(root);
            while(!s.empty())
            {
                cur=s.top();
                if( (cur->left==NULL&&cur->right==NULL) 
                || (pre!=NULL&& (pre==cur->left||pre==cur->right) ) )
                {
                    res.push_back(cur->val);
                    s.pop();
                    pre=cur;
                }
                else
                {
                    if(cur->right!=NULL)
                    {
                        s.push(cur->right);
                    }
                    if(cur->left!=NULL)
                    {
                        s.push(cur->left);
                    }
                }
            }
            return res;
        }
    };

[Link 1]: https://leetcode.com/problems/binary-tree-postorder-traversal/
[Link 2]: http://blog.csdn.net/zhangxiao93/article/details/52734630

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode - Medium - 145. Binary Tree Postorder Traversal

Topic Stack, Tree Description [https://leetcode.com/problems/binary-tree-postorde

川长思鸟来/ 2022年12月27日 12:41/ 0 赞/ 138 阅读

相关 leetCode解题报告之Binary Tree Postorder Traversal

题目： Binary Tree Postorder Traversal Given a binary tree, return the postorder tra

川长思鸟来/ 2022年08月25日 15:57/ 0 赞/ 61 阅读

相关 LeetCode145-Binary-Tree-Postorder-Traversal

LeetCode 145 : Binary Tree Postorder Traversal Given a binary tree, return the postord

本是古典何须时尚/ 2022年08月04日 12:49/ 0 赞/ 24 阅读

相关 leetcode 145. Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values. For example:

﹏ヽ暗。殇╰゛Y/ 2022年07月27日 15:55/ 0 赞/ 159 阅读

相关 LeetCode145—Binary Tree Postorder Traversal

原题 [原题链接][Link 1] > Given a binary tree, return the postorder traversal of its nodes

叁歲伎倆/ 2022年07月16日 04:22/ 0 赞/ 139 阅读

相关 [leetcode-二叉树后序遍历]--145. Binary Tree Postorder Traversal

Question 145. Binary Tree Postorder Traversal > Given a binary tree, return the postord

爱被打了一巴掌/ 2022年07月12日 03:29/ 0 赞/ 153 阅读

相关 [leetcode-二叉树后序遍历]--145. Binary Tree Postorder Traversal

Question 145. Binary Tree Postorder Traversal > Given a binary tree, return the postord

客官°小女子只卖身不卖艺/ 2022年07月12日 03:29/ 0 赞/ 134 阅读

相关 leetcode 145. Binary Tree Postorder Traversal 二叉树后续遍历

Given a binary tree, return the postorder traversal of its nodes’ values. For example:

快来打我*/ 2022年06月08日 06:24/ 0 赞/ 181 阅读

相关 68. Binary Tree Postorder Traversal

68. Binary Tree Postorder Traversal Description Given a binary tree, return th

叁歲伎倆/ 2022年05月27日 04:55/ 0 赞/ 174 阅读

相关 145. Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values. Example:

小鱼儿/ 2022年05月04日 01:58/ 0 赞/ 141 阅读