0.引言
- 110.平衡二叉树
- 二叉树的所有路径
- 404.左叶子之和
- 513.找树左下角的值
1.# 平衡二叉树
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Easy (57.50%) | 1267 | - |
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树*每个节点 *的左右两个子树的高度差的绝对值不超过 1 。
示例 1：
image.png
输入：root = [3,9,20,null,null,15,7]
输出：true
示例 2：
image.png
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
示例 3：
输入：root = []
输出：true
提示：
- 树中的节点数在范围
[0, 5000]内 -10<sup>4</sup> <= Node.val <= 10<sup>4</sup>
1.1.递归法
/*
* @lc app=leetcode.cn id=110 lang=cpp
*
* [110] 平衡二叉树
*/
// @lc code=start
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
bool isBalanced(TreeNode* root) {
if (root == nullptr) return true;
bool res = true;
dfs(root, res);
return res;
}
private:
// 以触底反弹的后续遍历进行，同时使用左右子树的思想，使用引用保存结果
int dfs(TreeNode* node, bool& res) {
if (node== nullptr ) {
return 0;
}
int left_depth = dfs(node->left, res);
int right_depth = dfs(node->right, res);
if (std::abs(right_depth - left_depth) > 1) res = false;
return 1 + std::max(left_depth, right_depth);
}
};
// @lc code=end
这个题用迭代法就不是很直观了。
2. 二叉树的所有路径
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Easy (70.69%) | 910 | - |
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1：
image.png
输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]
示例 2：
输入：root = [1]
输出：["1"]
提示：
- 树中节点的数目在范围
[1, 100]内 -100 <= Node.val <= 100
2.1.递归法
/*
* @lc app=leetcode.cn id=257 lang=cpp
*
* [257] 二叉树的所有路径
*/
// @lc code=start
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
std::vector<std::string> res;
dfs(root, "", res);
return res;
}
private:
// 很明显是使用前序遍历
void dfs(TreeNode* node, std::string one_path,
std::vector<std::string>& paths) {
if (node->left == nullptr && node->right == nullptr) {
one_path += std::to_string(node->val);
paths.push_back(one_path);
return;
}
// 隐式回溯
if (node->left) dfs(node->left, one_path + std::to_string(node->val) + "->", paths);
if (node->right) dfs(node->right, one_path + std::to_string(node->val) + "->", paths);
}
};
// @lc code=end
3. 左叶子之和
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Easy (62.04%) | 571 | - |
给定二叉树的根节点 root ，返回所有左叶子之和。
示例 1：
输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
示例 2:
输入: root = [1]
输出: 0
提示:
- 节点数在
[1, 1000]范围内 -1000 <= Node.val <= 1000
3.1.递归法
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (root == nullptr) return 0;
int sum = 0;
dfs(root, false, sum);
return sum;
}
private:
// 前序遍历
void dfs(TreeNode* node, bool is_left_node, int& sum) {
if (node->left == nullptr && node->right == nullptr) {
if (is_left_node) {
sum += node->val;
}
return;
}
if (node->left) dfs(node->left, true, sum);
if (node->right) dfs(node->right, false, sum);
}
};
4.找树左下角的值
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Medium (73.97%) | 447 | - |
给定一个二叉树的 根节点 root，请找出该二叉树的 **最底层 最左边 **节点的值。
假设二叉树中至少有一个节点。
示例 1:
image.png
输入: root = [2,1,3]
输出: 1
示例 2:
image.png
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
提示:
- 二叉树的节点个数的范围是
[1,10<sup>4</sup>] -2<sup>31</sup> <= Node.val <= 2<sup>31</sup> - 1
4.1.递归法
/*
* @lc app=leetcode.cn id=513 lang=cpp
*
* [513] 找树左下角的值
*/
// @lc code=start
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
int depth = 0, res;
dfs(root, false, 1, depth, res);
return res;
}
private:
// 前序遍历
void dfs(TreeNode* node, bool is_left_node, int cur_depth, int& depth,
int& res) {
if (node->left == nullptr && node->right == nullptr) {
if (cur_depth > depth) {
depth = cur_depth;
res = node->val;
}
return;
}
if (node->left) dfs(node->left, true, cur_depth + 1, depth, res);
if (node->right) dfs(node->right, false, cur_depth + 1, depth, res);
}
};
// @lc code=end
