递归/非递归总结"/>
【转载】二叉树各种遍历递归/非递归总结
本篇文章主要复习（学习）二叉树相关内容：
- 二叉树的先序、中序、后序遍历（递归与非递归实现），层序遍历（换行）
- 在二叉树中找到一个节点的后继节点
- 二叉树的序列化与反序列化
- 判断一颗二叉树是否平衡二叉树、搜索二叉树、完全二叉树
- 已知一颗完全二叉树，求其节点个数，要求时间复杂度严格小于O(N)O(N)
- 折纸问题
二叉树的各种遍历
二叉树的先序遍历，递归与非递归实现
所谓先序遍历，即先打印根节点，再分别打印左子树和右子树。递归实现很简单，代码如下：
1
2
3
4
5
6
7
8
9
| // 先序遍历，递归实现
void prev_order_recursion(TreeNode* root)
{if (root == NULL)return;cout << root->val << endl;prev_order_recursion(root->left);prev_order_recursion(root->right);
}
|
至于非递归实现，我们可以利用栈。首先将根节点入栈，然后循环执行以下过程：
- 从栈中弹出一个节点并打印；
- 如果左右孩子不为空，先入栈右孩子，再入栈左孩子；
- 跳到1继续执行，直到栈为空。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| // 先序遍历，非递归实现
void prev_order_nonrecursion(TreeNode* root)
{if (root == NULL)return;stack<TreeNode*> s;s.push(root);while (!s.empty()){root = s.top();s.pop();cout << root->val << endl;if (root->right)s.push(root->right);if (root->left)s.push(root->left);}
}
|
二叉树的中序遍历，递归与非递归实现
所谓中序遍历，即先打印左子树，再打印根节点，最后打印右子树。递归实现也很简单：
1
2
3
4
5
6
7
8
9
| // 中序遍历，递归实现
void median_order_recursion(TreeNode *root)
{if (root == NULL)return;median_order_recursion(root->left);cout << root->val << endl;median_order_recursion(root->right);
}
|
非递归实现稍微麻烦点。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| // 中序遍历，非递归实现
void median_order_nonrecursion(TreeNode *root)
{stack<TreeNode*> s;while (root || !s.empty()){while (root){s.push(root);root = root->left;}root = s.top();s.pop();cout << root->val << endl;root = root->right;}
}
|
先将整棵树的最左分支入栈，最后入栈的那个节点一定是会打印的，然后因为该结点可能有右子树，所以要对其右子树进行同样的操作打印该右子树，最后当栈为空并且当前节点也为空时结束循环。
二叉树的后序遍历，递归与非递归实现
后序遍历先打印左子树，再打印右子树，最后打印根节点。递归实现同样简单：
1
2
3
4
5
6
7
8
9
| // 后序遍历，递归实现
void post_order_recursion(TreeNode *root)
{if (root == NULL)return;post_order_recursion(root->left);post_order_recursion(root->right);cout << root->val << endl;
}
|
后序遍历的非递归实现是最难的。因为在递归实现中，一个节点实际上出现了三次：刚开始遍历到一个节点算一次，遍历完左子树之后返回到该结点是另一次，遍历完右子树之后回到该结点是第三次。后序遍历就是在第三次访问到该结点时才打印该结点。而我们用栈时实际上只能访问一个节点两次。这就需要我们用精细的流程控制来解决。有两种思路解决这个问题。
第一种思路：对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问， 因此其右孩子还未被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就 保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是 否是第一次出现在栈顶。代码如下：
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
28
29
30
31
32
33
34
35
36
37
| struct HelpNode
{TreeNode *node; // 访问到的二叉树节点bool is_first; // 该结点是否第一次访问
};// 后序遍历，非递归实现，第一种思路
void post_order_nonrecursion_1(TreeNode *root)
{stack<HelpNode *> s;HelpNode *h;while (root || !s.empty()){while (root){h = new HelpNode();h->is_first = true;h->node = root;s.push(h);root = root->left;}h = s.top();s.pop();if (h->is_first){h->is_first = false;s.push(h); // 重新入栈root = h->node->right; // 对右子树进行同样的操作}else{ // 左右子树都已经访问过了，可以直接打印当前节点了cout << h->node->val << endl;root = NULL; // 设置为NULL，下次循环会直接弹出当前节点的父节点}}
}
|
第二种思路：要保证根结点在左孩子和右孩子访问之后才能访问，对任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存 在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了 每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。如何判断该结点的左右孩子时候都被访问过了呢？只要用一个变量保存上一次访问的节点即可。如果上一次访问的是当前节点的左孩子或者右孩子，那么可以确定当前节点的左右孩子一定都被访问过了（因为左孩子一定在右孩子之前被访问，左右孩子一定在根节点之前被访问）。代码如下：
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
| // 后序遍历，非递归实现，第二种思路
void post_order_nonrecursion_2(TreeNode *root)
{if (root == NULL)return;stack<TreeNode *> s;s.push(root);TreeNode *prev = NULL; // 上一次访问的节点while (!s.empty()){root = s.top();if ((root->left == NULL && root->right == NULL) ||(prev != NULL && (prev == root->left || prev == root->right))){s.pop();cout << root->val << endl;prev = root;}else{if (root->right)s.push(root->right);if (root->left)s.push(root->left);}}
}
|
二叉树的层序遍历
所谓层序遍历，即按照一层一层的顺序打印二叉树的节点，例如有以下一颗二叉树：
层序遍历的结果为1,2,3,4,5,6,7。我们还要求按照节点出现的行换行，即上述结果应该为
1
2, 3
4, 5, 6
7
层序遍历实现思路很简单，利用队列，每个节点打印之后将其左子树和右子树分别入队。要实现换行则稍微麻烦些。定义两个变量，last和nlast，nlast始终指向队列中最后一个元素，last指向当前行的最后一个元素。当当前打印节点来到当前行的最后一个元素时，nlast一定指向下一行的最后一个元素。这时换行并更新last为nlast代码如下：
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
28
29
30
31
| // 层序遍历(换行)
void level_order(TreeNode *root)
{if (root == NULL)return;TreeNode *last, *nlast = NULL;queue<TreeNode *> q;q.push(root);last = root;while (!q.empty()){root = q.front();q.pop();cout << root->val << " ";if (root->left){q.push(root->left);nlast = root->left;}if (root->right){q.push(root->right);nlast = root->right;}if (root->val == last->val){cout << endl;last = nlast;}}
}
|
在二叉树中找到一个节点的后继节点
给定一个二叉树的节点结构如下：
1
2
3
4
5
6
7
8
9
| struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode *parent;TreeNode() = default;TreeNode(int x) : val(x) {}
};
|
其中parent指针指向其父节点，根节点的parent指针指向NULL。所谓二叉树中一个节点的后继节点即为二叉树的中序遍历中该结点的后一个节点。
这道题要分两种情况：当前节点有右子树，则当前节点的下一个节点就是其右子树的最左边的节点；当前节点没有右子树，则当前节点的后继节点为当前节点到根节点的路径上第一个左分支的父节点，比如有如下的二叉树：
7的后继节点就是2，因为2->4这个分支是7这个节点到根节点的路径上的第一个左分支。实现代码如下：
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
28
| // 返回以指定节点为根的树的最左边节点
TreeNode *most_left_node(TreeNode *node)
{while (node->left){node = node->left;}return node;
}// 二叉树中节点的后继节点
TreeNode *sucess_node(TreeNode *node)
{if (node == NULL)return NULL;if (node->right)return most_left_node(node->right);else{TreeNode *parent = node->parent;while (parent != NULL && parent->left != node){node = parent;parent = node->parent;}return parent;}
}
|
二叉树的序列化与反序列化
我们有一颗二叉树，如何将其以字符串的形式保存到磁盘上？又如何将一个磁盘上的字符串恢复成一颗二叉树？这个生成保存的字符串的过程叫做序列化，从字符串恢复的过程叫做反序列化。序列化与反序列化的方法很多，这里以先序遍历序列化与反序列化为例，其它都很类似。
先序遍历序列化
先序遍历过程中，将每个节点写入字符串，一个节点数据结束写入”_”，遇到NULL写入”#”。比如下面这颗树：
先序遍历序列化的结果为：1_2_4_#_7_#_#_#_3_5_#_#_6_#_#_。代码如下：
1
2
3
4
5
6
7
8
9
10
11
| // 先序遍历序列化
string prev_order_serialization(TreeNode *root)
{string ret = "";if (root == NULL)return "#_";ret += (to_string(root->val) + "_");ret += prev_order_serialization(root->left);ret += prev_order_serialization(root->right);return ret;
}
|
反序列化的过程也很类似，我们可以用一个队列来保存所有的数据，可以确定第一个元素一定是根节点，第二个元素一定是根节点的左子树，第三个元素一定是根节点的右子树。可以用如下的递归方式来实现：
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| // 先序遍历反序列化
TreeNode *deserialization(string &str)
{auto string_v = split(str, "_");queue<string> q;for (auto s : string_v)q.push(s);return do_deserialization(q);
}TreeNode *do_deserialization(queue<string> &q)
{string val = q.front();q.pop();if (val == "#")return NULL;TreeNode *node = new TreeNode(stoi(val));node->left = do_deserialization(q);node->right = do_deserialization(q);return node;
}vector<string> split(const string& str, const string& delim)
{ //将分割后的子字符串存储在vector中vector<string> res;if ("" == str) return res;string strs = str; //扩展字符串以方便检索最后一个分隔出的字符串size_t pos;size_t size = strs.size();for (int i = 0; i < size; ++i) {pos = strs.find(delim, i); //pos为分隔符第一次出现的位置，从i到pos之前的字符串是分隔出来的字符串if (pos != string::npos) { //如果查找到，如果没有查找到分隔符，pos为string::nposstring s = strs.substr(i, pos - i);//*****从i开始长度为pos-i的子字符串res.push_back(s);//两个连续空格之间切割出的字符串为空字符串，这里没有判断s是否为空，所以最后的结果中有空字符的输出，i = pos + delim.size() - 1;}}return res;
}
|
二叉树的判断相关
判断一颗二叉树是否平衡二叉树
所谓平衡二叉树是指树中每个节点的高度差都不超过1。为了解决这道题，我们需要一个函数，计算一个树的高度，当左右子树的高度差大于1时表示一棵树不是平衡二叉树。代码如下：
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
| struct ReturnData
{bool is_balance; // 当前树是否平衡int height; // 当前树的高度ReturnData(bool is_b, unsigned int h) : is_balance(is_b), height(h) {}
};// 判断一棵树是否平衡二叉树
bool is_balance(TreeNode *root)
{return get_height(root).is_balance;
}ReturnData get_height(TreeNode *node)
{if (node == NULL)return ReturnData(true, 0);auto l = get_height(node->left);if (!l.is_balance)return ReturnData(false, 0); // 如果不平衡，没必要更新高度，直接返回就可以了auto r = get_height(node->right);if (!r.is_balance || abs(l.height - r.height) > 1)return ReturnData(false, 0);return ReturnData(true, max(l.height, r.height) + 1);
}
|
在这里，我们定义了一个新的数据类型来保存get_height()函数的返回值。这是因为如果不平衡，我们没必要更新高度，直接返回就可，但是如果平衡，我们还需要左右子树的高度信息来判断当前节点是否平衡。
判断一颗二叉树是否搜索二叉树
所谓搜索二叉树是指一个节点的左子树所有节点都比当前节点小，右子树的所有节点都比当前节点大。
这个还是比较简单的，只要中序遍历出来结果是升序就OK了。代码如下：
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
28
29
30
31
| // 判断一棵树是否二叉搜索树
bool is_bst(TreeNode *root)
{auto ret = median_order_recursion_with_return(root);if (ret.size() < 2)return true;// 判断是否升序int prev = ret[0];for (size_t i = 1; i < ret.size(); ++i){auto cur = ret[i];if (prev > cur)return false;prev = cur;}return true;
}// 中序遍历，不打印数据，将数据保存到vector中
vector<int> median_order_recursion_with_return(TreeNode *root)
{vector<int> ret;if (root == NULL)return ret;auto temp = median_order_recursion_with_return(root->left);ret.insert(ret.end(), temp.begin(), temp.end());ret.push_back(root->val);temp = median_order_recursion_with_return(root->right);ret.insert(ret.end(), temp.begin(), temp.end());return ret;
}
|
判断一颗二叉树是否完全二叉树
对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
为了判断一棵树是不是完全二叉树，我们层序遍历这棵树。在层序遍历的过程中，判断节点的左右孩子是否存在，如果左孩子不存在，但是右孩子存在，则该树一定不是完全二叉树；如果左孩子存在但是右孩子不存在或者左右孩子都存在，则后面出现的节点一定都得是叶子节点。代码如下：
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
| // 判断一棵树是否为完全二叉树
bool is_cbt(TreeNode *root)
{if (root == NULL)return true;queue<TreeNode *> q;q.push(root);bool status = false; // 是否出现了某个节点有左孩子但是没有右孩子或者左右孩子都没有？while (!q.empty()){root = q.front();q.pop();if (status && (root->left || root->right))return false; // 后续节点不都是叶节点if (root->right && !root->left)return false; // 有右孩子但是没有左孩子if ((root->left && !root->right) || (!root->left && !root->right))status = true;if (root->left)q.push(root->left);if (root->right)q.push(root->right);}return true;
}
|
求完全二叉树的节点个数
给定一棵完全二叉树，计算出节点个数。要求时间复杂度严格小于O(N)O(N)。
如果没有时间复杂度的限制，我们完全可以遍历这棵树，计算出节点个数。但是这严格小于O(N)O(N)的时间复杂度的限制下，遍历的方式就不可行了。我们知道，如果是一棵满二叉树，节点个数是2h−12h−1，其中hh为树的高度。我们可以利用这个信息来计算完全二叉树的节点个数。具体过程如下：首先，计算出整棵树的高度hh，然后计算以当前节点为根的二叉树的右子树的最左分支的高度hrhr，如果hr=hhr=h，那么可以肯定当前节点的左子树是一棵高为h−1h−1的完全二叉树，可以利用公式计算出节点数，然后在递归计算右子树的节点数；如果hr≠hhr≠h，那么可以肯定当前节点的右子树是一棵高为h−2h−2的完全二叉树，同样可以利用公式计算右子树的节点数，再递归计算左子树的节点数。代码如下：
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
28
29
30
31
32
33
34
35
36
37
38
39
| // 计算一棵完全二叉树的节点数
int num_node_of_cbt(TreeNode *root)
{int h = most_left_height(root); // 计算当前树的高度（即是最左边分支的高度）return do_compute_node(root, h);
}// 递归计算节点数
int do_compute_node(TreeNode *root, int h)
{if (root == NULL)return 0;int hr = most_left_height(root->right);int left_num, right_num;if (hr == h){left_num = static_cast<int>(pow(2, h - 1)) - 1;right_num = do_compute_node(root->right, h - 1);}else{left_num = do_compute_node(root->left, h - 1);right_num = static_cast<int>(pow(2, h - 2)) - 1;}return left_num + 1 + right_num;
}int most_left_height(TreeNode *root)
{if (root == NULL)return 0;int h = 1;while (root){++h;root = root->left;}return h;
}
|
这种方式每次递归需要遍历O(logN)O(logN)个节点，总共最多递归O(logN)O(logN)次，总时间复杂度为O((logN)2)O((logN)2)。远小于O(N)O(N)。
发布评论