二叉树3大遍历：先序，中序，后序
非递归版本：http://08643.cn/p/373a002c401b
先序：
class Solution {
public:
vector<int> ans;
std::stack<TreeNode *> s;
vector<int> preorderTraversal(TreeNode * root) {
// write your code here
auto cur=root;
while(cur||s.size())
{
while(cur)
{
ans.push_back(cur->val);
s.push(cur);
cur=cur->left;
}
cur=s.top();
s.pop();
cur=cur->right;
}
return ans;
}
};
中序
class Solution {
public:
/**
* @param root: A Tree
* @return: Inorder in ArrayList which contains node values.
*/
vector<int> ans;
stack<TreeNode *> s;
vector<int> inorderTraversal(TreeNode * root) {
// write your code here
auto cur=root;
while(cur||s.size())
{
while(cur)
{
s.push(cur);
cur=cur->left;
}
cur=s.top();
s.pop();
ans.push_back(cur->val);
cur=cur->right;
}
return ans;
}
};
后序遍历
class Solution {
public:
/**
* @param root: A Tree
* @return: Postorder in ArrayList which contains node values.
*/
vector<int> ans;
std::stack<TreeNode *> s;
vector<int> postorderTraversal(TreeNode * root) {
// write your code here
auto cur=root;
TreeNode * last=NULL;
while(cur||s.size())
{
while(cur)
{
s.push(cur);
cur=cur->left;
}
cur=s.top();
if(cur->right==NULL||cur->right==last)
{
ans.push_back(cur->val);
s.pop();
last=cur;
cur=NULL;
}
else
cur=cur->right;
}
return ans;
}
};
- 二叉树的最近公共祖先
