首页 > 其他 > 详细

LintCode_68 二叉树中序遍历

时间:2016-05-01 13:36:16      阅读:211      评论:0      收藏:0      [点我收藏+]

题目

给出一棵二叉树,返回其节点值的后序遍历。

思路

后序比较麻烦 需要另外一个变量来记录当前节点入栈的次数

设计pair<TreeNode*, int> p;

p.first 为二叉树节点

p.second 为当前节点入栈的次数

C++代码

vector<int> postorderTraversal(TreeNode *root) {
    // write your code here
    vector<int> vec;
    stack<pair<TreeNode*, int>> s;
    s.push(make_pair(root,0));
    while(root && !s.empty())
    {
        TreeNode* p = s.top().first;
        int times = s.top().second;
        s.pop();
        if(0 == times)  //如果第一次入栈
        {
            s.push(make_pair(p,1));  //第二次入
            if(p->right) s.push(make_pair(p->right,0));
            if(p->left) s.push(make_pair(p->left,0));
        }
        else vec.push_back(p->val);
    }
    return vec;
}

  

 

LintCode_68 二叉树中序遍历

原文:http://www.cnblogs.com/Smallhui/p/5450353.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!