题目链接:110.平衡二叉树
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
文章讲解/视频讲解:https://programmercarl.com/0110.%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91.html
用递归的方式进行判断:记录当前节点左右子树的高度h1,h2,如果h1和h2的高度差绝对值不超过1,则说明当前节点及其子树可构成一个平衡二叉树。记当前节点的高度为max(h1, h2) + 1,再进行递归判断。
class Solution {
public:
bool isBalanced(TreeNode* root) {
if(root == nullptr) return true;
int height;
return dfs(root, height);
}
bool dfs(TreeNode* node, int& height){
if(node == nullptr){
height = 0;
return true;
}
int height1, height2;
bool lSuccess = dfs(node->left, height1);
bool rSuccess = dfs(node->right, height2);
height = max(height1, height2) + 1;
return lSuccess && rSuccess && (abs(height1 - height2) <= 1);
}
};
题目链接:257. 二叉树的所有路径
给你一个二叉树的根节点 root
,按 任意顺序 ,返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
文章讲解/视频讲解:https://programmercarl.com/0257.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%89%80%E6%9C%89%E8%B7%AF%E5%BE%84.html
用递归的方式进行遍历,可以采用前序遍历。记录下从根节点到叶节点沿途的路径,返回结果。具体见代码。
这里采用前序遍历来解决,那么也可以用迭代的前序遍历来做。
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
if(root == nullptr) return {};
string path;
vector<string> results;
dfs(root, path, results);
return results;
}
void dfs(TreeNode* node, string path, vector<string>& results){
if(node->left == nullptr && node->right == nullptr){
path += "->";
path += to_string(node->val);
results.push_back(path.substr(2, path.size() - 2));
return;
}
path += "->";
path += to_string(node->val);
if(node->left != nullptr) dfs(node->left, path, results);
if(node->right != nullptr) dfs(node->right, path, results);
}
};
题目链接:404.左叶子之和
给定二叉树的根节点 root
,返回所有左叶子之和。
文章讲解/视频讲解:https://programmercarl.com/0404.%E5%B7%A6%E5%8F%B6%E5%AD%90%E4%B9%8B%E5%92%8C.html
用递归的思路来解决。每一次递归的处理中,对于当前节点,标记其来自于左节点或者右节点,如果当前节点属于叶子节点,且标记为左节点,则累加结果。
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if(root == nullptr) return 0;
int sum = 0;
dfs(root, 2, sum);
return sum;
}
void dfs(TreeNode* node, int dir, int& sum){
// 定义dir = 0为左节点,dir = 1为右节点, dir = 2表示根节点
if(dir == 0 && node->left == nullptr && node->right == nullptr){
sum += node->val;
return;
}
if(node->left) dfs(node->left, 0, sum);
if(node->right) dfs(node->right, 1, sum);
}
};