二叉树中序遍历，先序遍历，后序遍历（递归栈，非递归栈，Morris Traversal）

我就是我 2021-11-10 16:32 281阅读 0赞

### 例题 ###

*  中序遍历[94. Binary Tree Inorder Traversal][]
 *  先序遍历[144. Binary Tree Preorder Traversal][]
 *  后序遍历[145. Binary Tree Postorder Traversal][]
    
    ### 递归栈 ###
    
    递归函数栈的方法很基础，写法也很简单，三种遍历方式之间只需要改变一行代码的位置即可
    
    #### 中序遍历 ####

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: void inorder(TreeNode* root, vector<int>& v){ if(root != nullptr) { inorder(root->left, v); v.push_back(root->val); // 改变位置的代码 inorder(root->right, v); } } vector<int> inorderTraversal(TreeNode* root) { vector<int> v; inorder(root, v); return v; } };

#### 先序遍历 ####

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: void inorder(TreeNode* root, vector<int>& v){ if(root != nullptr) { v.push_back(root->val); inorder(root->left, v); inorder(root->right, v); } } vector<int> inorderTraversal(TreeNode* root) { vector<int> v; inorder(root, v); return v; } };

#### 后序遍历 ####

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: void inorder(TreeNode* root, vector<int>& v){ if(root != nullptr) { inorder(root->left, v); inorder(root->right, v); v.push_back(root->val); } } vector<int> inorderTraversal(TreeNode* root) { vector<int> v; inorder(root, v); return v; } };

### 非递归栈 ###

当树的深度过大时，函数栈可能会溢出，这时候需要我们使用数据结构中的栈，来模拟节点在栈中的压入和弹出

#### 中序遍历 ####

cur指针时刻指向需要处理的节点  
如果当前节点不为空，则压入栈中，并改变cur指针指向其左节点  
如果当前节点为空，也代表空节点的中序遍历自动完成，无需压栈，这时候需要弹出栈顶的节点，保存栈顶节点的值，并更改cur指向其右子树，以完成右子树的中序遍历

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> v; stack<TreeNode*> s; TreeNode* cur = root; while(cur || !s.empty()){ if(cur){ s.push(cur); cur = cur->left; } else { cur = s.top(); s.pop(); v.push_back(cur->val); cur = cur->right; } } return v; } };

#### 先序遍历 ####

先序遍历与中序遍历代码相比只改变了保存节点的值的代码的位置，当先访问根的时候就记录节点，而不是等左子树遍历完，弹出根节点的时候再记录

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> v; stack<TreeNode*> s; TreeNode* cur = root; while(cur || !s.empty()){ if(cur){ v.push_back(cur->val); s.push(cur); cur = cur->left; } else { cur = s.top(); s.pop(); cur = cur->right; } } return v; } };

#### 后序遍历 ####

因为后序遍历的压栈顺序是左-右-根，由于先遍历完左子树，然后遍历完右子树，然后才能处理当前节点，为了和之前的代码的结构保持一致，我们可以反向处理，也就是按根-右-左的顺序压栈，  
结果反向输出即可

/** * Definition for a binary tree node. * 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> v; stack<TreeNode*> s; TreeNode* cur = root; while(cur || !s.empty()){ if(cur){ v.push_back(cur->val); s.push(cur); cur = cur->right; } else { cur = s.top(); s.pop(); cur = cur->left; } } reverse(v.begin(), v.end()); // 反向输出结果 return v; } };

### Morris Traversal ###

线索二叉树，O(n)时间，常数空间  
[Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间）][Morris Traversal_O_1]  
就是当前节点的中序遍历前驱节点，如果此前驱节点的右指针为空，则将此前驱节点的右指针指向当前节点  
当寻找当前节点的中序遍历前驱节点时，发现能循环到自己，说明左子树已经遍历完，需要遍历右子树

#### 中序遍历 ####

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> inorderTraversal(TreeNode* root) { TreeNode* cur, *prev; vector<int> v; cur = root; prev = nullptr; while(cur){ if(cur->left == nullptr){ v.push_back(cur->val); cur = cur->right; } else { prev = cur->left; while(prev->right != nullptr && prev->right != cur) prev = prev->right; if(prev->right == nullptr){ prev->right = cur; cur = cur->left; } else { v.push_back(cur->val); prev->right = nullptr; cur = cur->right; } } } return v; } };

#### 先序遍历 ####

同样先序遍历与中序遍历相比也只需要改变一行代码的位置

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> preorderTraversal(TreeNode* root) { TreeNode* cur, *prev; vector<int> v; cur = root; prev = nullptr; while(cur){ if(cur->left == nullptr){ v.push_back(cur->val); cur = cur->right; } else { prev = cur->left; while(prev->right != nullptr && prev->right != cur) prev = prev->right; if(prev->right == nullptr){ v.push_back(cur->val); prev->right = cur; cur = cur->left; } else { prev->right = nullptr; cur = cur->right; } } } return v; } };

#### 后序遍历 ####

后序遍历需要反向输出cur->left到cur的中序前驱结点之间的路径

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: void reverse_traverse_reverse(TreeNode* cur, vector<int>& v){ TreeNode* prev = nullptr; while(cur){ auto right = cur->right; cur->right = prev; prev = cur; cur = right; } cur = prev; prev = nullptr; while(cur){ auto right = cur->right; cur->right = prev; v.push_back(cur->val); prev = cur; cur = right; } } vector<int> postorderTraversal(TreeNode* root) { TreeNode* cur, *prev; vector<int> v; cur = new TreeNode(-1); prev = nullptr; cur->left = root; while(cur){ if(cur->left == nullptr){ cur = cur->right; } else { prev = cur->left; while(prev->right != nullptr && prev->right != cur) prev = prev->right; if(prev->right == nullptr){ prev->right = cur; cur = cur->left; } else { prev->right = nullptr; reverse_traverse_reverse(cur->left, v); cur = cur->right; } } } return v; } };

### 总结 ###

三种遍历方式中，后序遍历的处理比较麻烦，但是无论是使用递归栈，非递归栈还是Morris Traversal，代码的结构都是一样的，中序和前序甚至只有一行代码位置的差别  
使用栈的版本中，最坏空间复杂度为O（n）链型，平均空间复杂度为O（lgn）  
Morris Traversal空间复杂度为O(1)

转载于:https://www.cnblogs.com/qbits/p/11163161.html

[94. Binary Tree Inorder Traversal]: https://leetcode.com/problems/binary-tree-inorder-traversal/
[144. Binary Tree Preorder Traversal]: https://leetcode.com/problems/binary-tree-preorder-traversal/
[145. Binary Tree Postorder Traversal]: https://leetcode.com/problems/binary-tree-postorder-traversal/
[Morris Traversal_O_1]: https://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html