Posted on 2014-01-11 02:52
Uriel 阅读(130)
评论(0) 编辑 收藏 引用 所属分类:
LeetCode
裸的二叉树后序遍历
RE无穷多次,注意判空树!!!
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode *tp[1010];
vector<int> postorderTraversal(TreeNode *root) {
int k = 0;
vector<int> que;
if(root == NULL) return que;
TreeNode *p = root, *pre = NULL;
tp[k++] = p;
while(k) {
TreeNode *cur = tp[k - 1];
if((cur->left == NULL && cur->right == NULL) || (pre != NULL && (pre == cur->left || pre == cur->right))) {
que.push_back(cur->val);
--k;
pre = cur;
}
else {
if(cur->right != NULL) tp[k++] = cur->right;
if(cur->left != NULL) tp[k++] = cur->left;
}
}
return que;
}
};