题目描述
Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1
2
/
3
return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?
给出一个二叉树，返回这棵二叉树的先序遍历结果。
递归太平凡了，能不能用迭代？
代码及注释
1. 栈+迭代
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
// 最终返回的遍历结果
vector<int> result;
// 存储所有 中间节点 的栈(存储的都是栈节点指针)
stack<TreeNode *> s;
// 如果当前树顶非空
if(root != nullptr)
// 则把当前 树顶节点压栈
s.push(root);
// 只要当前栈非空
while(!s.empty()){
// 记录当前栈顶节点指针
TreeNode * p = s.top();
// 记录完后退栈
s.pop();
// 刚刚记录退栈的节点值加入遍历结果
result.push_back(p->val);
// 把刚刚记录退栈的节点的左右子节点压栈（注意顺序）
if(p->right != nullptr)
s.push(p->right);
if(p->left != nullptr)
s.push(p->left);
}
return result;
}
};
2.Morris 线索二叉树
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
// 最终返回的遍历结果
vector<int> result;
// Morris先序遍历需要一个 “当前节点” 控制所有流程
TreeNode *cur = root;
// 还需要一个 ”前驱节点” 控制刚刚访问的节点
TreeNode *prev = nullptr;
// 停止条件：“当前节点” 为空
while(cur != nullptr){
// 如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点
if(cur->left == nullptr){
// 输出当前节点
result.push_back(cur->val);
// 更新刚刚访问的节点
prev = cur;
// 将其右孩子作为当前节点
cur = cur->right;
}
else{
// 下面三行寻找当前节点cur的前驱 node节点
// 当前节点左子树不为空，则在左子树中寻找当前结点的前驱节点
// 这个节点其实就是当前节点左子树最右边的节点
TreeNode *node = cur->left;
while(node->right != nullptr && node->right != cur)
node = node->right;
// 如果没有线索化，则建立线索
if(node->right == nullptr){
// 输出当前节点(这里是和中序唯一区别)
result.push_back(cur->val);
// 建立线索
node->right = cur;
// 记录已被访问的节点
prev = cur;
// 由于左孩子不为空，则将左孩子作为当前结点
cur = cur->left;
}
// 已经线索化只能说明找到的node=cur，则回退
else{
// 删除线索
node->right = nullptr;
// 回退
cur = cur->right;
}
}
}
return result;
}
};
分析
栈+迭代
pop出栈顶节点，记录它的值，然后将它的左右子节点push入栈，以此类推。线索二叉树
- 如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。
- 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。输出当前节点（在这里输出，这是与中序遍历唯一一点不同）。当前节点更新为当前节点的左孩子。
b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空。当前节点更新为当前节点的右孩子。 - 重复以上1、2直到当前节点为空。
线索二叉树
