二叉树中序遍历三种方法

// 递归遍历
vector<int> v;
vector<int> inorderTraversal(TreeNode* root) {
if(!root) return v;
inorderTraversal(root->left);
v.push_back(root->val);
inorderTraversal(root->right);
return v;
}

// 使用栈的迭代
vector<int> inorderTraversal(TreeNode* root) {
vector<int> v;
if(!root) return v;
TreeNode* temp = root;
stack<TreeNode*> s;
while(true){
while(temp){
s.push(temp);
temp = temp->left;
}
if(s.empty()) break;
temp = s.top();
s.pop();
v.push_back(temp->val);
temp = temp->right;
}
return v;
}

第二种使用栈的方式
```cpp
struct Command {
string s;
TreeNode* node;
Command( string s, TreeNode* node ): s(s), node(node) {}
};
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
if(root == NULL)
return res;
stack<Command> stk;
stk.push(Command("go", root));
while( !stk.empty()) {
Command commmand = stk.top();
stk.pop();
if(commmand.s == "print") {
res.push_back(commmand.node -> val);
} else {
if(commmand.node->right) {
stk.push(Command("go", commmand.node->right));
}
stk.push(Command("print", commmand.node));
if(commmand.node->left) {
stk.push(Command("go", commmand.node->left));
}
}
}
return res;
}
};
</code></pre>

// 迭代 morris traversal,无栈
vector<int> inorderTraversal(TreeNode* root) {
vector<int> v;
if(!root) return v;
TreeNode* temp = root, *prev;
while(temp){
if(!temp->left){
v.push_back(temp->val);
temp = temp->right;
}else{
prev = temp->left;
while(prev->right&&(prev->right != temp))
prev = prev->right;
if(!prev->right){
prev->right = temp;
temp = temp->left;
}else{
v.push_back(temp->val);
prev->right = NULL;
temp = temp->right;
}
}
}
}
// 三个方法来自 leetcode
```

先序遍历
后序遍历

Hello world!
文章已创建 200

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部