今日题目
| 题目 | 难度 | 备注 |
|---|---|---|
| 226. 翻转二叉树 | 简单 | |
| 101. 对称二叉树 | 简单 | |
| 222. 完全二叉树的节点个数 | 简单 | ⭐⭐⭐ |
| 110. 平衡二叉树 | 简单 | ⭐⭐⭐ |
| 257. 二叉树的所有路径 | 简单 | 代码优化能力 |
树篇 Ⅱ
- 今日题目
- 题目：226. 翻转二叉树
- 一、源代码
- 二、代码思路
- 题目：101. 对称二叉树
- 一、源代码
- 二、代码思路
- 三、优化代码
- 题目：222. 完全二叉树的节点个数
- 一、源代码
- 二、代码思路
- 三、优化思路
- 四、优化代码
- 题目：110. 平衡二叉树
- 一、源代码
- 二、代码思路
- 三、优化思路
- 四、优化代码
- 题目：257. 二叉树的所有路径
- 一、源代码
- 二、代码思路
- 三、优化思路
- 四、优化代码
题目：226. 翻转二叉树
226. 翻转二叉树 - 力扣（LeetCode）
一、源代码
class Solution {
private:
void DFS(TreeNode* root) {
if (!root) return; // 为空指针结束
if (root->left || root->right) { // 左孩子或者右孩子不为空则交换左右孩子
swap(root->left,root->right);
}
DFS(root->left);
DFS(root->right);
}
public:
TreeNode* invertTree(TreeNode* root) {
DFS(root);
return root;
}
};
二、代码思路
先序遍历二叉树，若访问到空指针则结束，若访问结点的左孩子或者右孩子不为空则交换左右孩子。
题目：101. 对称二叉树
101. 对称二叉树 - 力扣（LeetCode）
一、源代码
class Solution {
private:
bool isSym(TreeNode* root1, TreeNode* root2) {
if (!root1 && !root2) return true;
if ((root1 && !root2) || (!root1 && root2)) return false;
if (root1->val != root2->val) return false;
bool l = isSym(root1->left,root2->right); // 判断root1 和 root2 的孩子结点对称否
bool r = isSym(root1->right,root2->left);
if (!l || !r) return false;
return true;
}
public:
bool isSymmetric(TreeNode* root) {
return isSym(root->left,root->right);
}
};
二、代码思路
递归判断，每次处理一层。对每一层：
① 如果root1 和 root2 都为空，则对称。
② 如果 root1 和 root2 一个为空，一个不为空，则不对称。
③ 如果 root1 和 root2 的孩子结点不对称，则不对称。
三、优化代码
bool isSym(TreeNode* root1, TreeNode* root2) {
if (!root1 && !root2) return true;
if (!root1 || !root2) return false;
return root1->val == root2->val && isSym(root1->left,root2->right)
&& isSym(root1->right,root2->left);
}
题目：222. 完全二叉树的节点个数
222. 完全二叉树的节点个数 - 力扣（LeetCode）
一、源代码
class Solution {
private:
int BFS(TreeNode* root) {
if (!root) return 0;
queue<TreeNode*> q;
q.push(root);
int cnt = 0;
while(!q.empty()) {
TreeNode* now = q.front();
q.pop();
++cnt;
if (now->left) q.push(now->left);
if (now->right) q.push(now->right);
}
return cnt;
}
public:
int countNodes(TreeNode* root) {
return BFS(root);
}
};
二、代码思路
BFS 遍历树，记录结点数
三、优化思路
因为为完全二叉树，所以最多只有一个非满二叉子树，其余都是满二叉子树。所以只需判断当前节点引导的子树是不是满二叉树，是的话直接返回子树的结点，不是的话就往下遍历。此时间复杂度为 O(logn ^ 2)
四、优化代码
class Solution {
public:
int countNodes(TreeNode* root) {
if (!root) return 0;
int lDepth = 0;
int rDepth = 0;
TreeNode* node = root;
while (node->left) { // 获取左子树高度
lDepth += 1;
node = node->left;
}
node = root;
while (node->right) { // 获取右子树高度
rDepth += 1;
node = node->right;
}
if (lDepth == rDepth) { // 如果左子树高度等于右子树高度 说明为满二叉树，则直接返回 结点数
return (int)pow(2, lDepth + 1) - 1;
}else { // 否则返回左子树结点 + 右子树结点 + 1
return countNodes(root->left) + countNodes(root->right) + 1;
}
}
};
题目：110. 平衡二叉树
110. 平衡二叉树 - 力扣（LeetCode）
一、源代码
class Solution {
int getHight(TreeNode* root,int h) {
if (!root) return h;
int l = getHight(root->left,h+1);
int r = getHight(root->right,h+1);
return l > r ? l : r;
}
public:
bool isBal = true;
bool isBalanced(TreeNode* root) {
if (!root) return true;
if (abs(getHight(root->left, 0) - getHight(root->right, 0)) > 1) isBal = false;
isBalanced(root->left);
isBalanced(root->right);
return isBal;
}
};
// 可优化写成
int getHight(TreeNode* root) {
if (!root) return 0;
return max(getHight(root->left), getHight(root->right)) + 1;
}
bool isBalanced(TreeNode* root) {
if (!root) return true;
else return abs(getHight(root->left) - getHight(root->right)) <= 1)
&& isBalanced(root->left) && isBalanced(root->right);
}
二、代码思路
自顶向下遍历树的各结点（先序遍历），对每一结点，判断左右子树的高度差是否小于等于 1
三、优化思路
自顶向下递归，因此对于同一个节点，函数 getHight 会被重复调用，导致时间复杂度较高。如果使用自底向上的做法（后序遍历），则对于每个节点，函数 getHight只会被调用一次。
先序遍历不管怎么样都会计算一遍再说，后序遍历可以口口相传及时止损
四、优化代码
class Solution {
public:
int height(TreeNode* root) { // 通过返回的高度判断是否为平衡二叉树，若为则返回高度，否则返回-1
if (root == NULL) {
return 0;
}
int leftHeight = height(root->left); // 后序遍历
int rightHeight = height(root->right);
if (leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1) {
return -1; // 左子树或右子树非平衡二叉树，或者该结点引导的二叉树非平衡，则返回 -1；
} else {
return max(leftHeight, rightHeight) + 1; // 否则返回 当前结点高度
}
}
bool isBalanced(TreeNode* root) {
return height(root) >= 0;
}
};
题目：257. 二叉树的所有路径
257. 二叉树的所有路径 - 力扣（LeetCode）
一、源代码
class Solution {
private:
vector<vector<int>> ans;
void DFS(TreeNode* root,vector<int> vi) { // 遍历树，并记录各从根节点到叶子节点的路径上的结点
if (!root) return;
vi.push_back(root->val);
if (!root->left && !root->right) {
ans.push_back(vi);
}
if (root->left) DFS(root->left, vi);
if (root->right) DFS(root->right, vi);
}
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<int> vi;
vector<string> res;
DFS(root,vi);
for (int i = 0; i < ans.size(); i++) { // 获取路径，并存入 vector<string> 中
string rode = "";
for (int j = 0; j < ans[i].size(); j++) {
rode += to_string(ans[i][j]);
if (j < ans[i].size() - 1) {
rode += "->";
}
}
res.push_back(rode);
}
return res;
}
};
二、代码思路
利用 DFS 遍历树，并记录各从根节点到叶子节点的路径上的结点。然后访问结点获取路径，并存入 vector<string> 中。
三、优化思路
先是vector<vector<int>> ans 数组存各路径的结点，然后遍历ans 数组取出各结点形成路径，这太麻烦了。为什么不直接形成路径，然后存起来呢？这就不用定义vector<vector<int>> ans 数组了。时间复杂度和空间复杂度都会得到减少。
四、优化代码
class Solution {
public:
void construct_paths(TreeNode* root, string path, vector<string>& paths) {
if (root != nullptr) {
path += to_string(root->val);
if (root->left == nullptr && root->right == nullptr) { // 当前节点是叶子节点
paths.push_back(path); // 把路径加入到答案中
} else {
path += "->"; // 当前节点不是叶子节点，继续递归遍历
construct_paths(root->left, path, paths);
construct_paths(root->right, path, paths);
}
}
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> paths;
construct_paths(root, "", paths);
return paths;
}
};
