树的各种算法非递归实现

树的各种算法的非递归实现总结,包括中序遍历,判断是否为子树等等

前序遍历

通过一个栈实现,每次入栈的同时将节点的值放入结果集中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
if (!root)
return {};
vector<int> res;
stack<TreeNode *> st;
TreeNode * p = root;
while(p || !st.empty()){
while(p != nullptr){
st.push(p);
res.push_back(p->val);
p = p->left;
}
p = st.top();
st.pop();
p = p->right;
}
return res;
}
};

中序遍历

通过一个栈实现,首先一直将根结点的左子树放入栈中,直到叶子结点。跟前序遍历的不同点在于放入结果集的时间。前序遍历是在入栈时放入,而中序遍历是在出栈时放入。

然后从栈中取出该结点并从栈中弹出,以及将该结点的值插入结果集中,同时将该结点的右孩子放入栈中(通过将p=p->right,然后执行上面的while(p)循环实现)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> inorderTraversal(TreeNode* root) {
if (!root)
return {};
stack<TreeNode *> st;
vector<int> res;
TreeNode * p = root;
while(!st.empty() || p){
while(p){
st.push(p);
p = p->left;
}
if (!st.empty()){
p = st.top();
st.pop();
res.emplace_back(p->val);
p = p->right;
}
}
return res;
}

后序遍历

对前序遍历进行一些修改即可以实现。

  • 放入d队列的顺序相反,先放入右节点,再放入左节点。
  • 每次都是插入到结果集的最前面。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
vector<int> postorderTraversal(TreeNode* root) {
if (!root)
return {};
vector<int> res;
deque<TreeNode *> d, t;
res.push_back(root->val);
TreeNode * p = root;
while(p || !t.empty()){
if (p){
if (p->right) //与前序遍历不同之处
d.push_back(p->right);
if (p->left)
d.push_back(p->left);
p = nullptr;
}
while(!d.empty()){
t.push_front(d.back());
d.pop_back();
}
if (!t.empty()){
p = t.front();
t.pop_front();
res.insert(res.begin(), p->val); //与后序遍历不同之处
}
}
return res;
}
zxp wechat
欢迎关注微信公众号!