首页 > 代码库 > [Leetcode][Tree][Binary Tree Postorder Traversal]
[Leetcode][Tree][Binary Tree Postorder Traversal]
二叉树的后续遍历
1、递归版本
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: void dfsPostorderTraversal(TreeNode *now, vector<int> &result) { if (now == NULL) { return; } dfsPostorderTraversal(now->left, result); dfsPostorderTraversal(now->right, result); result.push_back(now->val); } vector<int> postorderTraversal(TreeNode *root) { vector<int> result; dfsPostorderTraversal(root, result); return result; }};CE一次。。。为什么我总是CE呢。。因为写完之后觉得程序太简单，所以不想检查。。
2、迭代版本
/** * Definition for binary tree * 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> result; TreeNode *now, *pre; stack<TreeNode*> s; now = root; pre = NULL; //while (now != NULL || !s.empty()) { do { while (now != NULL) { s.push(now); now = now->left; } pre = NULL; while (!s.empty()) { now = s.top(); if (now->right != pre) { now = now->right; break; } else { result.push_back(now->val); pre = now; s.pop(); } } } while(!s.empty()); return result; }};后续遍历需要两个指针来记录状态now和pre，还有3个循环的边界，感觉这个程序可以写成很多不同的版本。
关键是如何判断now这个点的左子树和右子树都已经被访问过了。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。