01二叉树的属性
# 01 二叉树的属性
最为常见的树就是二叉树，这种树的每个节点最多有两个子节点，二叉树可以看成是单链表的升级版，因为他和链表的主要区别就是多了一个子节点的指针。
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) {}
};
二叉树的属性包含：树深度、树直径、树节点数、左叶子节点、对称性、平衡性和路径问题等。这些二叉树的属性都可通过递归或者迭代的方式求得或验证。
# 104 二叉树的最大深度 (opens new window)
求一个二叉树的最大深度。
输入是一个二叉树，输出是一个整数，表示该树的最大深度。
输入： [3,9,20,null,null,15,7]，
3 / \ 9 20 / \ 15 7输出：3
解释：返回它的最大深度 3
解析：
采用深度优先搜索，其子问题是：左子树和右子树的最大深度 l 和 r，那么该二叉树的最大深度即为 max(l,r)+1。中止条件是访问的节点为空，推出递归。
class Solution {
public:
int maxDepth(TreeNode* root) {
if(!root){
return 0;
}
return max(maxDepth(root->left),maxDepth(root->right)) + 1;
}
};
# 110 平衡二叉树 (opens new window)
判断一个二叉树是否平衡。树平衡的定义是，对于树上的任意节点，其两侧节点的最大深度的差值不得大于 1。
输入是一个二叉树，输出一个布尔值，表示树是否平衡。
输入：root = [1,2,2,3,3,null,null,4,4] 输出：false
解析：
本题的思路类似104 二叉树的最大深度 (opens new window)，不同的是在获取子树深度时要对当前左右子树的深度进行比较，如果还未遍历完二叉树就已经发现左右子树不平衡，则直接返回-1，避免再继续往下计算子树深度。
提前返回-1中断子树深度计算要注意的是：第一次返回-1的判断条件是abs(left - right) > 1，但是在往上回溯深度计算结果的过程中，如果出现了中断，那么回溯结果为 -1，这时表明下层子树出现了不平衡情况，所以上层返回-1的判断条件是left == -1 || right == -1
class Solution {
public:
int treeDepth(TreeNode* node){
if(!node){
return 0;
}
int l = treeDepth(node->left);
int r = treeDepth(node->right);
if(l==-1 || r==-1 || abs(l-r)>1){
return -1;
}
return max(l,r)+1;
}
bool isBalanced(TreeNode* root) {
return treeDepth(root) != -1;
}
};
# 543 二叉树的直径 (opens new window)
求一个二叉树的最长直径。直径的定义是二叉树上任意两节点之间的无向距离。
输入是一个二叉树，输出一个整数，表示最长直径。
输入：给定二叉树
1 / \ 2 3 / \ 4 5输出： 3
解释：它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
解析：
本题可以直接转化为左子树最大深度与右子树最大深度之和，所以在递归计算子树深度时，更新的最长直径值和递归返回的值是不同的。这是因为待更新的最长直径值是经过该子树根节点的最长直径（即两侧长度）；而函数返回值是以该子树根节点为端点的最长直径值（即一侧长度），使用这样的返回值才可以通过递归更新父节点的最长直径值）。
class Solution {
public:
int maxDepth(TreeNode* root, int& diameter){
if(!root){
return 0;
}
int l = maxDepth(root->left,diameter);
int r = maxDepth(root->right,diameter);
// 更新当前节点的最长直径
diameter = max(l+r,diameter);
return max(l,r)+1;
}
int diameterOfBinaryTree(TreeNode* root) {
int diameter = 0;
maxDepth(root,diameter);
return diameter;
}
};
# 101 对称二叉树 (opens new window)
判断一个二叉树是否对称。
输入一个二叉树，输出一个布尔值，表示该树是否对称。
1 / \ 2 2 / \ / \ 3 4 4 3二叉树
[1,2,2,3,4,4,3]是对称的
解析：
本题可以将二叉树是否对称转化为其左右子树是否对称，本质上还是树的递归问题，但是递归过程中涉及到比较。对两个子树进行比较判断是否相等或对称的解法一般可以按照如下四步：
- 如果两个子树都为空指针，则它们相等或对称，从根节点递归到叶子节点时都是相等的
- 如果两个子树只有一个为空指针，则它们不相等或不对称，一棵子树却胳膊少腿肯定不相等
- 如果两个子树根节点的值不相等，则它们不相等或不对称，出现比较位置不同值直接返回false
- 根据相等或对称要求，进行递归处理；相等就是左子树的左节点和右子树的左节点比较，左子树的右节点和右子树的右节点比较；对称就是左子树的左节点和右子树的右节点比较，左子树的右节点和右子树的左节点比较
需要注意的是前三个判断步骤不能调换顺序，因为有一个为空范围大于均为空，如果有空就无法取值。
class Solution {
public:
bool isSymmetric(TreeNode* left, TreeNode* right){
if(!left && !right){
return true;
}else if(!left || !right){
return false;
}else if(left->val != right->val){
return false;
}
return isSymmetric(left->left,right->right) && isSymmetric(left->right,right->left);
}
bool isSymmetric(TreeNode* root) {
if(!root){
return true;
}
return isSymmetric(root->left,root->right);
}
};
# 572 另一棵树的子树 (opens new window)
给定两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树
输入两棵二叉树，输出一个布尔值表示 root 树中是否包含 subRoot 树
输入：root = [3,4,5,1,2], subRoot = [4,1,2] Tree root Tree subRoot 3 4 / \ / \ 4 5 1 2 / \ 1 2 输出：true
解析：
本题是101 对称二叉树 (opens new window)的变种题，解题分为两个步骤，第一步遍历 root 树找和 subRoot 相同的根节点，第二步判断 root 中子树是否和 subRoot 相同。
判断两颗二叉树是否相同和判断二叉树是否对称思路一致，递归对比参与比较的两个节点值，最终递归将节点全部顺利比较完成则两颗二叉树相同，否在有一棵树先被遍历完成或者出现节点值不相同的情况，那么这两颗树也不相同。
遍历二叉树寻找相同子树的过程就是递归遍历每一颗子树，遍历过程中不断与 subRoot 进行比较得出结果。
public:
bool isSameTree(TreeNode* root, TreeNode* subRoot){
if(!root && !subRoot){
return true;
}else if(!root || !subRoot){
return false;
}else if(root->val!=subRoot->val){
return false;
}
return isSameTree(root->left,subRoot->left) && isSameTree(root->right,subRoot->right);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if(!subRoot){
return true;
}else if(!root){
return false;
}
return isSameTree(root,subRoot) || isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}
};
# 404 左叶子之和 (opens new window)
给定一个二叉树，计算该树的所有左叶子之和
输入一颗二叉树，输出一个整数表示所有左叶子之和
输入： 3 / \ 9 20 / \ 15 7 输出：24 解释：在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
解析：
本题的关键就在于利用左叶子节点的定义进行有条件递归遍历二叉树，同时要判断一个节点是不是叶子节点，定义一个辅助函数如果该节点没有子节点则说明该节点是叶子节点。
如果一个节点是左叶子节点，那么它是某个节点的左子节点，并且它还是一个叶子结点。
根据此定义，在递归遍历过程中，如果一个节点有左子节点，且该节点是一个叶子节点，那么将该左子节点加到累和中；假若该左子节点不是叶子节点，则以该左子节点为根节点递归查找左叶子节点。
如果一个节点有右子节点，且该节点是一个叶子节点，不进行累和且终止往下递归；假若该右子节点不是叶子节点，则将该右子节点为根节点递归查找左叶子节点。
class Solution {
public:
bool isLeafNode(TreeNode* root){
return !root->left && !root->right;
}
int sumOfLeftLeaves(TreeNode* root) {
if(!root){
return 0;
}
int ans = 0;
if(root->left){
ans += isLeafNode(root->left)?root->left->val:sumOfLeftLeaves(root->left);
}
if(root->right){
ans += isLeafNode(root->right)?0:sumOfLeftLeaves(root->right);
}
return ans;
}
};
# 437 路径总和 III (opens new window)
给定一个整数二叉树，求有多少条路径节点值的和等于给定值。
输入一个二叉树和一个给定整数，输出一个整数，表示有多少条满足条件的路径。
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 输出：3
解析：
本题的关键在于计算路径和，所以在递归每个节点时，需要分情况考虑：
- 如果选取该节点加入路径，则之后必须继续加入连续节点，或停止加入节点
- 如果不选取该节点加入路径，则对其左右节点进行重新进行考虑
因此一个方便的方法是创建一个辅函数，专门用来计算连续加入节点的路径。该辅助函数就是通过用给定值递归减去路径节点值，最终给定值减为0表示构成一条路径。
class Solution {
public:
int pathWithRoot(TreeNode* root, int sum){
if(!root){
return 0;
}
int count = 0;
// 如果当前节点值与路径和一致则形成一条路径
if(root->val == sum){
count = 1;
}else{
count = 0;
}
// 往左右子节点继续寻找路径
count += pathWithRoot(root->left, sum-root->val);
count += pathWithRoot(root->right, sum-root->val);
return count;
}
int pathSum(TreeNode* root, int targetSum) {
if(!root){
return 0;
}
// 将当前节点加入路径
int ans = 0;
ans = pathWithRoot(root,targetSum);
// 不将当前节点加入路径，从左右子节点开始寻找新路径
ans += pathSum(root->left,targetSum);
ans += pathSum(root->right,targetSum);
return ans;
}
};