摘要
- 平衡二叉树的左右子树的高度差不超过1
- 求二叉树的所有路径是回溯法的基础
- 判断当前节点是不是左叶子
LeetCode110 平衡二叉树
- 复习二叉树的高度和深度概念，借用代码随想录里的例子
image.png
-
关键概念
二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）
从0开始为边的条数，从1开始为节点数
-
二叉树的深度，在数值上等于二叉树的根节点的高度。
- 求深度是从上往下计算的，所以前序遍历的“中左右”对应着求深度的由父节点到子节点，即先计算父节点的深度（根节点的深度为1），然后将父节点的深度传递给左右子树。
- 求高度是从下往上计算的，所以后序遍历的“左右中”对应着求高度的先分别求左右子树的高度再返回给父节点。
- 二叉树的深度，在数值上等于二叉树根节点的高度，所以二叉树的深度也可以用后序遍历计算。
- 但真正求二叉树的深度的逻辑，应该是前序遍历。
平衡二叉树要通过每个节点的左右子树的高度来判断，而不是根节点的左右子树的高度差不超过1就是平衡二叉树，所以平衡二叉树也是要递归遍历每个节点的
image.png
上图为反例，上图所示的树不是平衡二叉树
- 求高度用后序遍历，并且需要在求高度的过程中判断当前节点的左右子树是不是平衡二叉树，如果当前节点的左右子树不是平衡二叉树，那当前树也不是平衡二叉树
递归法的题解代码如下
class Solution {
public:
int getAVLDepth(TreeNode* root) {
if (!root) return 0;
int leftDepth = getAVLDepth(root->left);
if (leftDepth == -1) return -1;
int rightDepth = getAVLDepth(root->right);
if (rightDepth == -1) return -1;
if (abs(leftDepth - rightDepth) > 1) return -1;
int depth = 1 + max(leftDepth, rightDepth);
return depth;
}
bool isBalanced(TreeNode* root) {
return getAVLDepth(root) != -1;
}
};
LeetCode257 二叉树的所有路径
- 这里需要计算的是从根节点到叶子节点的路径。
- 到达一个叶节点后，应该回溯到最近的一个非叶节点，再继续寻找未被访问的叶节点。
- 如此递归直到访问完所有叶节点。
- 从根节点开始，所以是根（父）节点先被处理，这里应该采用前序遍历“中左右”
- 递归法按如下三步确定代码的思路：
- 递归函数的参数和返回值：当前节点；当前保存的路径，保存答案路径的数组。
- 递归函数的终止条件：到达叶节点
- 单层递归的逻辑：将当前节点加入当前路径中，若当前节点为叶节点，则将当前路径存入答案数组后返回；若当前节点不为叶节点，则继续递归寻找叶节点，递归后将加入路径的节点弹出来完成回溯。
- 回溯与递归是一一对应，成对存在的。有一次递归，就应该有一次回溯。求二叉树的所有路径是回溯法的基础。
清晰的体现回溯法的题解代码如下
class Solution {
public:
void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {
path.push_back(cur->val); // 中，先将当前节点放入当前路径
// 终止条件，当前节点为叶节点时将当前路径放入答案数组
if (!cur->left && !cur->right) {
string sPath;
int size = path.size();
for (auto& iter : path) {
sPath += to_string(iter);
if (--size) sPath += "->";
}
result.push_back(sPath);
return;
}
// 向左找叶节点
if (cur->left) {
traversal(cur->left, path, result);
path.pop_back();// 回溯，将当前节点的左孩子弹出
}
// 向右找叶节点
if (cur->right) {
traversal(cur->right, path, result);
path.pop_back();// 回溯，将当前节点的右孩子弹出
}
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<int> path;
vector<string> result;
if (root) traversal(root, path, result);
return result;
}
};
- 通过传入参数不为引用，从而能隐式地实现回溯，代码如下。
class Solution {
public:
void traversal(TreeNode* cur, string path, vector<string>& result) {
path += to_string(cur->val);
if (!cur->left && !cur->right) {
result.push_back(path);
return;
}
if (cur->left) traversal(cur->left, path + "->", result);
if (cur->right) traversal(cur->right, path + "->", result);
}
vector<string> binaryTreePaths(TreeNode* root) {
string path;
vector<string> result;
if (root) traversal(root, path, result);
return result;
}
};
LeetCode404 左叶子之和
- 首先明确左叶子的定义：当前节点为叶节点，且为其父节点的左孩子。仅凭当前节点的保留的信息，只能判断当前节点是否是叶节点；只有通过当前节点的父节点，才能判断当前节点是否为左孩子。
- 初见题目时采用了前序遍历，直观理解为先。
- 递归函数的参数和返回值：参数为当前父节点，当前左叶子之和。无返回值。
- 递归的终止条件：前序遍历没有明显的终止条件，隐含在各个if的判空逻辑里。或者明显的写出当前节点为叶节点.
- 单层递归的处理逻辑：判断当前节点有左叶子，然后再去判断当前节点的左孩子是否有左叶子，右孩子是否有左叶子
前序遍历的题解代码如下
class Solution {
public:
void sumOfLeftLeavesWorkPlace(TreeNode* root, int& sum) {
if (root->left && !root->left->left && !root->left->right) {
sum += root->left->val;
}
else if (root->left) sumOfLeftLeavesWorkPlace(root->left, sum);
if (root->right) sumOfLeftLeavesWorkPlace(root->right, sum);
}
int sumOfLeftLeaves(TreeNode* root) {
int sum = 0;
if (root) sumOfLeftLeavesWorkPlace(root, sum);
return sum;
}
};
- 代码随想录的讲解采用的是后序遍历，其实这题只需要将左叶子统计出来就可以了，采用不同的遍历方式对应着不同的直观理解
- 前序遍历：以当前节点为父节点，判断当前节点是否有左叶子，再去判断当前节点的左孩子和右孩子是否有左叶子。自上而下
- 后序遍历：找到左叶子后，将左叶子的值返回给左叶子的父节点的那层递归，若左子树就是左叶子则直接取值（递归的终止条件之一）；然后找右子树的左叶子。
后序遍历的实现代码
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (root == NULL) return 0;
if (!root->left && !root->right) return 0;
int leftValue = sumOfLeftLeaves(root->left); // 左
// 左子树就是一个左叶子的情况
if (root->left && !root->left->left && !root->left->right) {
leftValue = root->left->val;
}
int rightValue = sumOfLeftLeaves(root->right); // 右
int sum = leftValue + rightValue; // 中
return sum;
}
};
