`
SunnyYoona
  • 浏览: 361523 次
社区版块
存档分类
最新评论

[LeetCode]145.Binary Tree Postorder Traversal

 
阅读更多

【题目】

Given a binary tree, return thepostordertraversal 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?

【代码】

/*********************************
*   日期:2014-12-07
*   作者:SJF0115
*   题号: 145.Binary Tree Postorder Traversal
*   来源:https://oj.leetcode.com/problems/binary-tree-postorder-traversal/
*   结果:AC
*   来源:LeetCode
*   总结:
**********************************/
#include <iostream>
#include <malloc.h>
#include <vector>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> v;
        stack<TreeNode *> stack;
        TreeNode *p = root;
        TreeNode *q;
        do{
            //遍历左子树
            while(p != NULL){
                stack.push(p);
                p = p->left;
            }
            q = NULL;
            while(!stack.empty()){
                p = stack.top();
                stack.pop();
                // 右子树是否为空或者已访问过
                if(p->right == q){
                    v.push_back(p->val);
                    //保留访问过的节点
                    q = p;
                }
                else{
                    //当前节点不能访问,p节点重新入栈
                    stack.push(p);
                    //处理右子树
                    p = p->right;
                    break;
                }//if
            }//while
        }while(!stack.empty());//while
        return v;
    }
};

//按先序序列创建二叉树
int CreateBTree(TreeNode* &T){
    char data;
    //按先序次序输入二叉树中结点的值(一个字符),‘#’表示空树
    cin>>data;
    if(data == '#'){
        T = NULL;
    }
    else{
        T = (TreeNode*)malloc(sizeof(TreeNode));
        //生成根结点
        T->val = data-'0';
        //构造左子树
        CreateBTree(T->left);
        //构造右子树
        CreateBTree(T->right);
    }
    return 0;
}

int main() {
    Solution solution;
    TreeNode* root(0);
    CreateBTree(root);
    vector<int> v = solution.postorderTraversal(root);
    for(int i = 0;i < v.size();i++){
        cout<<v[i]<<endl;
    }
}

【代码二】

/*------------------------------------------------
*   日期:2015-03-25
*   作者:SJF0115
*   题目: 145.Binary Tree Postorder Traversal
*   来源:https://oj.leetcode.com/problems/binary-tree-postorder-traversal/
*   结果:AC
*   来源:LeetCode
*   博客:
------------------------------------------------------*/
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

// 二叉树节点结构
struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> result;
        if(root == nullptr){
            return result;
        }//if
        stack<TreeNode*> s;
        s.push(root);
        TreeNode *node;
        while(!s.empty()){
            node = s.top();
            s.pop();
            result.insert(result.begin(),node->val);
            // 左子树
            if(node->left){
                s.push(node->left);
            }//if
            // 右子树
            if(node->right){
                s.push(node->right);
            }//if
        }//while
        return result;
    }
};
// 1.创建二叉树
void CreateTree(TreeNode* &root){
    int val;
    //按先序次序输入二叉树中结点的值,‘-1’表示空树
    cin>>val;
    // 空节点
    if(val == -1){
        root = nullptr;
        return;
    }//if
    root = new TreeNode(val);
    //构造左子树
    CreateTree(root->left);
    //构造右子树
    CreateTree(root->right);
}
int main() {
    freopen("C:\\Users\\Administrator\\Desktop\\c++.txt", "r", stdin);
    TreeNode* root = nullptr;
    vector<int> result;
    // 创建二叉树
    CreateTree(root);

    Solution solution;
    result = solution.postorderTraversal(root);
    for(int i = 0;i < result.size();++i){
        cout<<result[i]<<" ";
    }
    cout<<endl;
    return 0;
}



分享到:
评论

相关推荐

    145.Binary Tree Postorder Traversal二叉树的后序遍历【LeetCode单题讲解系列】

    145.Binary_Tree_Postorder_Traversal二叉树的后序遍历【LeetCode单题讲解系列】

    leetcode卡-LeetCode:我的LeetCode解决方案

    leetcode卡 LeetCode 记录一下再LeetCode上刷的题,坚持每天刷一道吧 2017.06.12 打卡[LeetCode 2. Add Two Numbers], Linked list 2017.06.13 打卡[LeetCode 200. Number of Islands], BFS 2017.06.14 打卡...

    leetcode-tree

    144-Binary Tree Preorder Traversal94-Binary Tree Inorder Traversal145-Binary Tree Postorder Traversal(后续的非递归时间不够可以先跳过,有点难)层次遍历,队列辅助,相当于广搜。102-Binary Tree Level ...

    LeetCode最全代码

    * [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...

    四平方和定理leetcode-leetcode-practice:个人LeetCode练习代码

    106.construct-binary-tree-from-inorder-and-postorder-traversal (从中序与后序遍历序列构造二叉树) 112.path-sum (路径总和) 116.populating-next-right-pointers-in-each-node (填充每个节点的下一个右侧节点

    cpp-算法精粹

    Construct Binary Tree from Inorder and Postorder Traversal 二叉查找树 Unique Binary Search Trees Unique Binary Search Trees II Validate Binary Search Tree Convert Sorted Array to Binary Search Tree ...

    LeetCodeSolution:LeetCode的部分解决方案

    Binary Tree Postorder Traversal (145) 要求不用递归实现后序遍历 后序是left-right-root,那么首先用修正的前序root-right-left,然后reverse一下,变成left-right-root就行了,代码如下: Factorial Trailing ...

    leetcode:LeetCode在线法官的Java解决方案

    Leetcode问题用JavaScript解决使用...二叉树后置遍历( https://leetcode.com/problems/binary-tree-postorder-traversal/ ) Node.js样式标准代码应遵循Node.js样式标准( https://github.com/felixge/node-style-gu

    LeetCode:LeetCode解决方案

    LeetCodeLeetCode solutions(Java)树Minimum Depth of Binary Tree栈evaluate-reverse-polish-notation穷举max-points-on-a-line链表sort-list排序insertion-sort-list树binary-tree-postorder-traversal树binary-...

    lrucacheleetcode-LeetCode_Note:leetcode个人笔记

    lru缓存leetcode LeetCode_Note leetcode 个人笔记 ...[106_construct-binary-tree-from-inorder-and-postorder-traversal.cpp] [107_binary-tree-level-order-traversal-ii.cpp] [108_convert-sorted

    gasstationleetcode-leetcode-in-niuke:在牛客网上的在线编程中的leetcode在线编程题解

    binary-tree-postorder-traversal 树 binary-tree-preorder-traversal 链表 linked-list-cycle-ii 链表 linked-list-cycle 链表 copy-list-with-random-pointer 复杂度 single-number 动态规划 candy 贪心 gas-...

    leetcode跳跃-Algorithm:算法学习,包括leetcode算法题,

    leetcode 跳跃 Algorithm 算法题解: 包括书籍算法, 程序员算法面试指南, 还有leetcode算法题 ...construct-binary-tree-from-inorder-and-postorder-traversal 无官方题解 116 populating-next-right-pointers-in-eac

    javalruleetcode-algorithm-java:leetcode刷题

    java lru leetcode ...Tree/BinaryTree BST HashTable Disjoint Set Trie BloomFilter LRU Cache Algorithm General Coding InOrder/PreOrder/PostOrder Traversal Greedy Recursion/Backtrace Breadth-fi

    【LeetCode】【树】106. 从中序与后序遍历序列构造二叉树

    https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ 2 题目描述 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 中序...

    poj与leetcode-coding_exercises:编码练习

    poj与leetcode 自述文件 介绍 本repo由鞠承佑、钟恺健、王少泽创建。 它在帐户SuanFaRuoji(算法弱鸡)下...└──889_construct_binary_tree_from_preorder_and_postorder_traversal └──zkj_python.py 我们的任务

Global site tag (gtag.js) - Google Analytics