二叉树遍历主要有四种:前序遍历,中序遍历,后序遍历,层序遍历。
1. 前序遍历(pre-order-traversal)
a. 递归算法
递归算法非常简单,不赘述。
本文 DoSomething 全部假定为按顺序输出一个vector。
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x):val(x), left(nullptr), right(nullptr) { }
};
class Solutions {
public:
vector<int> preorderTraversal(TreeNode* root){
if(root != nullprt) {
ret.push_back(root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
return ret;
}
private:
vector<int> ret;
};
b. 非递归算法
非递归算法需要用一个辅助栈,栈中先添加右边节点,再添加左边节点,因为栈后进先出,左边的节点先被遍历,所以要后进。
Solutions{
public:
vector<int> preorderTraversal(TreeNode* root) {
if (root != nullptr) {
st.push(root);
while(!st.empty()) {
TreeNode* tmp = st.top();
ret.push_back(tmp->val);
st.pop();
if (tmp->right) { st.push(tmp->right); }
if (tmp->left) { st.push(tmp->left); }
}
}
return ret;
}
private:
stack<TreeNode*> st;
vector<int> ret;
};
还有另一种非递归算法,先一直遍历左节点,若遇空节点,则返回到其父节点,然后再遍历右节点。
class Solutions {
public:
vector<int> preorderTraversal(TreeNode* root) {
if (root == nullptr) return ret;
while(root!=nullptr || !st.empty()){
if(root){
st.push(root);
ret.push_back(root->val);
root = root->left;
}
else{
root = st.top();
st.pop();
root = root->right;
}
}
return ret;
}
private:
vector<int> ret;
stack<TreeNode*> st;
};
2. 中序遍历(in-order-traversal)
a. 递归算法
class Solutions {
public:
vector<int> inorderTraversal(TreeNode* root) {
if (root != nullptr) {
midorderTraversal(root->left);
ret.push_back(root->val);
midorderTraversal(root->right);
}
return ret;
}
private:
vector<int> ret;
};
b. 非递归算法
算法思想:先深度遍历左边节点,当左孩子为空时,利用stack返回到其父节点,然后再遍历右孩子。
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
if (root == nullptr) return ret;
while(root || !st.empty()) {
while(root){
st.push(root);
root = root->left;
}
root = st.top();
ret.push_back(root->val);
st.pop();
root = root->right;
}
}
return ret;
}
private:
vector<int> ret;
stack<TreeNode* > st;
};
3. 后序遍历(post-order-traversal)
a. 递归算法
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
if (root == nullptr ) return ret;
postorderTraversal(root->left);
postorderTraversal(root->right);
ret.push_back(root->val);
return ret;
}
private:
vector<int> ret;
};
b. 非递归算法