代码随想录笔记|C++数据结构与算法学习笔记-二叉树(二)|二叉树层序遍历、226.翻转二叉树

二叉树层序遍历

文章链接：二叉树层序遍历

视频链接：讲透二叉树的层序遍历 | 广度优先搜索 | LeetCode：102.二叉树的层序遍历

• 102.二叉树的层序遍历
• 107.二叉树的层次遍历II
• 199.二叉树的右视图
• 637.二叉树的层平均值
• 429.N叉树的层序遍历
• 515.在每个树行中找最大值
• 116.填充每个节点的下一个右侧节点指针
• 117.填充每个节点的下一个右侧节点指针II
• 104.二叉树的最大深度
• 111.二叉树的最小深度

如何去层序遍历二叉树呢？如果依赖二叉树这种结构本身，无法层序保存结点的。我们需要借助一个队列来帮我们保存每一层里面遍历过的元素

队列模拟过程

他本质上是图论的广度优先搜索，也是依赖队列来去实现。

对于一个二叉树

​ A

/
B C
/ \ / \
D E F G

首先一个根结点A加入到队列，并且要记录我们的队列大小size = 1，然后我们把当前层的元素A弹出来加入到结果数组里

然后我们把第二层数据B、C加入到队列里，此时的size = 2，这个队列大小就记录着第二层的元素个数就是2，接下来我们遍历这个队列是只弹出2个元素，因为队列中的元素是变化的，所以我们一定要记录好该层的元素。

所以我们把B弹出，现在我们需要把下一层的元素加入到队列，所以当前队列的元素是[C D E]，如果没有size来记录每一层元素的个数，我们如何知道队列中的元素哪些是第二层哪些是第三层呢？刚好之前我们已经记录了第二层大小是2。所以现在我们弹出C。

然后把C的左右孩子加入到队列也就是[D E F G]，size = 4.就表示了我们的第三层有4个结点。然后我们把DEFG弹出。

那么按刚才的规则把DEFG都弹出之后，我们再一次记录栈的size。这个size就是第四层的结点数，在本题中很显然，没有第四层，所以栈也是空的，我们随后跳出循环即可。

伪代码实现

queue<TreeNode*> que;
if(root != NULL) que.push(root);//root不为空就把根结点加入到队列中
while(!que.empty)//如果队列中没有元素了，也就是说层序遍历没有元素添加到队列中了，层序遍历终止
{  
  size = que.size();
	vector<int> vec;//每层用一个一维数组保存
  while (size--)	//这里的循环条件千万不能写成que.size()因为队列的长度在不断变化
  {
    note = que.front(); que.pop();
    vec.push_back(node->val);//记录完本层结点后将结点的左右孩子加入到队列中
    
    if (node->left)	que.push(node->left);
    if (node->right) que.push(node->right);
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

C++实现

迭代法：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

递归法：

class Solution {
public:
    void order(TreeNode* cur, vector<vector<int>>& result, int depth)
    {
        if (cur == nullptr) return;
        if (result.size() == depth) result.push_back(vector<int>());
        result[depth].push_back(cur->val);
        order(cur->left, result, depth + 1);
        order(cur->right, result, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        int depth = 0;
        order(root, result, depth);
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

226.翻转二叉树

力扣题目链接

文章链接：226.翻转二叉树

视频链接：听说一位巨佬面Google被拒了，因为没写出翻转二叉树 | LeetCode：226.翻转二叉树

遍历顺序的重要性

一定要确认好遍历顺序。这道题目用前序和后序是最合适的，用中序遍历不太方便。

前序和中序遍历的代码实现

如果用递归遍历的话，一定要想好递归三部曲

• 确定递归函数的返回值和参数

​ 函数返回值是结点的定义，参数后面慢慢确定都无所谓

FreeNode* invertTree(TreeNode* root)
1

• 确定终止条件

​ 什么时候终止遍历呢，就是碰到空结点的时候

if (root == NULL) return root;
1

• 处理逻辑

​ 先写前序遍历：中左右，中间就是我们要处理的地方，处理的逻辑就是交换这个结点的两个孩子。

swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);
1
2
3

​ 然后是后序遍历：左右中

invertTree(root->left);
invertTree(root->right);
swap(root->left, root->right);
1
2
3

C++ 代码实现

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        swap(root->left, root->right);  // 中
        invertTree(root->left);         // 左
        invertTree(root->right);        // 右
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10

为什么不用中序遍历

左中右的遍历顺序，会导致，左子树被反复处理，右子树没被处理。

具体过程请参看视频：听说一位巨佬面Google被拒了，因为没写出翻转二叉树 | LeetCode：226.翻转二叉树

此时的代码应该写成

invertTree(root->left);
swap(root->left, root->right);
invertTree(root->left);	//为什么这里还处理左子树呢，因为现在的左子树其实是之前的右子树！
1
2
3

二叉树阶段性总结Part1

先做个标记，总结以后再写，感觉好难