代码随想录DAY14 - 二叉树 - 08/13

翻转二叉树

题干

思路

代码

方法一：层序遍历，迭代法

方法二：前序遍历递归法

拓展

对称二叉树

题干

思路

方法一：递归法

方法二：迭代法

代码

方法一：递归法

方法二：迭代法

二叉树的最大深度

题干

思路

代码

迭代法

递归法

N叉树的最大深度

题干

思路

代码

递归法

迭代法

二叉树的最小深度

题干

思路

代码

递归法

迭代法

翻转二叉树

题干

题目：给你一棵二叉树的根节点 root ，左右翻转这棵二叉树，并返回其根节点。

链接：. - 力扣（LeetCode）

思路

方法一迭代法：层序遍历二叉树，遍历到每一层结点的时候，交换每个结点的左右指针。

方法二递归法：前序遍历二叉树，每次遍历时翻转左右指针。

代码

方法一：层序遍历，迭代法

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (root == nullptr){return root;}TreeNode* cur;queue<TreeNode*> layer;layer.push(root);int count = 1; // 层数while (!layer.empty()){while (count--){cur = layer.front();layer.pop();swap(cur->left,cur->right); // 交换每个结点的左右指针// 让下一层的结点入队if (cur->left != nullptr) layer.push(cur->left);if (cur->right != nullptr) layer.push(cur->right);}count = layer.size(); // 记录一层的结点个数}return root;}
};

方法二：前序遍历递归法

class Solution {
public:TreeNode* invertTree(TreeNode* root) {// 中左右，先翻转中间结点的左右指针，再翻转左右子树if (root == nullptr) return root; // 当指针为空，递归结束swap(root->left,root->right);invertTree(root->left);invertTree(root->right);return root;}
};

拓展

递归法是否可以中序遍历来翻转左右指针？

不可以，因为有些结点的左右孩子会被反转两次。我们知道中序遍历是 “左中右” 的顺序，相当于先反转左子树，再反转中间结点，最后反转右子树。假设先反转了左子树，接着反转中间的根节点，此时左右子树已经被反转了，之后的右子树其实变成了以前的左子树，后续如果反转右子树，相当于把之前的左子树又反转了回来，那么之前的左子树就被反转了两次。

如果非得用中序遍历递归反转左右指针，在遍历完中间节点后，应该继反转的是左子树（即以前的右子树），而不是右子树。

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (root == NULL) return root;invertTree(root->left);         // 反转左子树swap(root->left, root->right);  // 反转中间结点invertTree(root->left);         // 注意！！！这里依然要遍历左子树，因为中间节点已经翻转了return root;}
};

对称二叉树

题干

给你一个二叉树的根节点 root ，检查它是否轴对称。

思路

如何判断是否对称？当左子树翻转后和右子树相同，即对称。

方法一：递归法

我们需要比较左子树和右子树是否呈镜像，问题可以分解为左子树的外侧和右子树的外侧是否相同、左子树的内侧和右子树的内侧是否相同。我们需要两个指针 left 和 right 分别遍历同侧的左右子树结点，并比较两节点是否相同。

递归法的遍历方式本质上是后序遍历，且只能是后序遍历。

为什么只能是后序遍历？

因为我们需要比较的是结点的左右孩子是否翻转相同，只有后序遍历的 “左右中” 顺序是先处理完左右孩子才返回给上一层的中间节点；如果是前序 “中左右” 和中序 “左中右” 的遍历方式，都需要先处理中间结点，无法先处理孩子结点。

什么时候要采用后序遍历？

当题目需要采集孩子信息向上一层返回时，都需要后序遍历。

方法二：迭代法

我们需要比较每一层的结点是否头尾两两相同，若是则对称。用两个指针 leftNode 和 rightNode 分别遍历左、右子树，用一个队列来存储每一层的结点，但存储的结点顺序并不是从左到右，而是头尾两两存储，（即同侧的两个结点会相邻存储在队列中），故每次对比同侧的结点时都是成对地从队列中取出结点比较。

代码

方法一：递归法

class Solution {
public:bool compare(TreeNode* a, TreeNode* b){if (a == nullptr && b == nullptr){// 两个结点都为空，则对称return true;} else if (a != nullptr && b != nullptr && a->val == b->val){// 如果值相同，比较当前两个结点的子树是否对称bool outside = compare(a->left,b->right); // 比较外侧bool inside = compare(a->right,b->left); // 比较内侧return outside&&inside; // 只有外侧和内测都相同，才是 true} else{// 其他情况：a空，b非空； a非空，b空； a，b值不等 就都为 falsereturn false;}}bool isSymmetric(TreeNode* root) {if (root == nullptr){return true;}return compare(root->left,root->right); // 传入根节点的左右子树}
};

方法二：迭代法

class Solution {
public:bool isSymmetric(TreeNode* root) {if (root == nullptr){return true;}queue<TreeNode*> layer; // 存储结点layer.push(root->left); // 插入左子树layer.push(root->right); // 插入右子树TreeNode* leftNode; // 遍历左子树TreeNode* rightNode; // 遍历右子树while (!layer.empty()){leftNode = layer.front();layer.pop();rightNode = layer.front();layer.pop();if (leftNode == nullptr && rightNode != nullptr){return false;} else if (leftNode != nullptr && rightNode == nullptr){return false;} else if (leftNode != nullptr && rightNode != nullptr && leftNode->val != rightNode->val){return false;} else if (leftNode == nullptr && rightNode == nullptr){// 两个结点均为空，对称，continuecontinue;} else{// 插入外侧结点layer.push(leftNode->left);layer.push(rightNode->right);// 插入内侧结点layer.push(leftNode->right);layer.push(rightNode->left);}}return true;}
};

二叉树的最大深度

题干

题目：给定一个二叉树 root ，返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

链接：. - 力扣（LeetCode）

思路

区分二叉树的最大深度和二叉树结点的高度

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）

方法一迭代法：我们在做层序遍历的拓展题时就求过二叉树的最大深度，只需要在层序遍历时记录二叉树的层数即可。

方法二递归法：求二叉树的最大深度，可以分解为子问题求左右子树的最大深度，每往下遍历一层则深度就加一，当结点为空则表示遍历到最底部，递归结束，返回 0。要清楚的是，这本质上是二叉树的后序遍历，也就是我们先求了子树的深度再返回给上一层的结点，所以是 “左右中” 的顺序。

代码

迭代法

class Solution {
public:int maxDepth(TreeNode* root) {// 如果根节点为空，直接返回空数组，如果不判空，后续会报错if (root == nullptr){return {};}TreeNode* cur = root; // 遍历每一个节点int count = 1; // 记录每一层的节点个数，第一层只有根节点，节点个数为 1queue<TreeNode*> tmpNode; // 存储每一层的节点tmpNode.push(root); // 初始只存储第一层的根节点int result = 0; // 存储层数// 当队列为空说明已经遍历完所有节点while (!tmpNode.empty()){result++; // 每循环一次说明就多了一层!!!!// 遍历当前层的节点while (count--){cur = tmpNode.front(); // 弹出队头tmpNode.pop(); // 弹出节点// 将左右孩子节点入队if (cur->left != nullptr){tmpNode.push(cur->left);}if (cur->right != nullptr){tmpNode.push(cur->right);}}count = tmpNode.size(); // 队列长度就是下一层的节点个数}return result;}
};

递归法

class Solution {
public:int maxDepth(TreeNode* root) {if (root == nullptr){return 0;}int leftDepth = maxDepth(root->left); // 求左子树的最大深度int rightDepth = maxDepth(root->right); // 求右子树的最大深度int depth = 1 + max(leftDepth,rightDepth); // 深度 + 1，是因为要加当前结点这一层 return depth; // 返回的是左右子树的最大值}
};

N叉树的最大深度

题干

题目：给定一个 N 叉树，找到其最大深度。最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

链接：. - 力扣（LeetCode）

思路

递归法：仍然是求子树的最大深度再返回给上一层结点，但是 N叉树可能有 N 个子树，所以需要递归求这 N 个子树的深度。

迭代法：也是用N叉树的层序遍历就可以求最大深度了。

代码

递归法

class Node { // N叉树的结点定义，如果在力扣里运行，记得去掉这部分，只是为了方便查看才放这
public:int val;vector<Node*> children; // N叉树的所有孩子结点Node() {}Node(int _val) {val = _val;}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};
class Solution {
public:int maxDepth(Node* root) {if (root == nullptr) return 0;int max = 0; // 求最大深度，初始为 0 for (int i = 0; i < root->children.size(); ++i) {// 递归求每个子树的深度int depth = maxDepth(root->children[i]);if (max < depth){max = depth;}}return 1+max;}
};

迭代法

class Solution {
public:int maxDepth(Node* root) {if (root == nullptr){return {};}Node* cur = root; // 注意数据类型为 Node！！！int count = 1; // 记录每一层的结点个数queue<Node*> tmpNode; // 存储每一层的节点tmpNode.push(root); // 初始只存储根节点int depth = 0; // 记录深度，初始化为 0while (!tmpNode.empty()){depth++; // 每循环一次，就是遍历下一层，深度加一while (count--){cur = tmpNode.front(); // 弹出队头tmpNode.pop();// N 叉树是将 0~N 个孩子结点入队，修改处！！！if (cur->children.size() > 0){for (Node* child : cur->children) {tmpNode.push(child);}}}count = tmpNode.size(); // 队列长度就是下一层的节点个数}return depth;}
};

二叉树的最小深度

题干

题目：给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

链接：. - 力扣（LeetCode）

思路

递归法：求二叉树的最小深度，可分解为求每个子树的最小深度。但容易犯的错误是，遇到左子树为空，而右子树非空的情况，左子树的深度视为 0 吗？不是，我们只有遇到 “叶子节点” 才算深度，所以当左子树为空，需要往右子树继续遍历求最小深度。

错误代码如下！！！

class Solution {
public:int minDepth(TreeNode* root) {if (root == nullptr) return 0;int leftDepth = minDepth(root->left);int rightDepth = minDepth(root->right);// 此时如果左子树为空，右子树非空，求出来的最小深度会是 0 ，是错误的int depth = min(leftDepth,rightDepth);return depth+1;}
};

迭代法：仍旧是层序遍历，只要遍历到叶子节点就暂停，不用遍历到最后一个结点。

代码

递归法

class Solution {
public:int minDepth(TreeNode* root) {if (root == nullptr) return 0;// 找叶子结点if (root->left == nullptr && root->right == nullptr) return 1;int depth;if (root->left != nullptr && root->right == nullptr){// 左子树非空，右子树空，要继续遍历记录左子树depth = minDepth(root->left);} else if (root->right != nullptr && root->left == nullptr){// 左子树空，右子树非空，要继续遍历右子树depth = minDepth(root->right);} else{// 左右子树都非空，则要比较求最小深度depth = min(minDepth(root->left), minDepth(root->right));}return depth+1;}
};

迭代法

class Solution {
public:int minDepth(TreeNode* root) {// 如果根节点为空，直接返回空数组，如果不判空，后续会报错if (root == nullptr){return {};}TreeNode* cur = root; // 遍历每一个节点int count = 1; // 记录每一层的节点个数，第一层只有根节点，节点个数为 1queue<TreeNode*> tmpNode; // 存储每一层的节点tmpNode.push(root); // 初始只存储第一层的根节点int result = 0; // 存储层数// 当队列为空说明已经遍历完所有节点while (!tmpNode.empty()){result++; // 每循环一次说明就多了一层!!!!// 遍历当前层的节点while (count--){cur = tmpNode.front(); // 弹出队头tmpNode.pop(); // 弹出节点// 判断当前结点是否为叶子结点，若是，则当前结点所在的层数即最小深度if (cur->left == nullptr && cur->right == nullptr){return result;}// 将左右孩子节点入队if (cur->left != nullptr){tmpNode.push(cur->left);}if (cur->right != nullptr){tmpNode.push(cur->right);}}count = tmpNode.size(); // 队列长度就是下一层的节点个数}return result;}
};