题一：leetcode：104（二叉树的最大深度）
(https://leetcode-cn.com/problems/longest-common-subsequence/)
题目描述：
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/
9 20
/
15 7
返回它的最大深度 3 。
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == nullptr) return 0;
return 1+max(maxDepth(root->left), maxDepth(root->right));
}
};
题二：leetcode：110（平衡二叉树）
(https://leetcode-cn.com/problems/balanced-binary-tree/)
题目描述：
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/
9 20
/
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/
2 2
/
3 3
/
4 4
返回 false 。
class Solution {
public:
bool isBalanced(TreeNode* root) {
int maxHeight = 0;
return isBalancedwithMaxHeight(root, maxHeight);
}
bool isBalancedwithMaxHeight(TreeNode* root, int& maxHeight)
{
if(root == nullptr) {maxHeight = 0; return true;}
int left = 0;
int right = 0;
if( isBalancedwithMaxHeight(root->left, left) &&isBalancedwithMaxHeight(root->right, right))
{
if(left-right > 1 || right-left > 1)
{
return false;
}
else
{
maxHeight = (left > right ? left : right) + 1;
return true;
}
}
else return false;
}
};
题三：leetcode：543（二叉树的直径）
(https://leetcode-cn.com/problems/diameter-of-binary-tree/)
题目描述：
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
示例 :
给定二叉树
1
/
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
int maxVal = 0;
diameter(root, maxVal);
return maxVal;
}
int diameter(TreeNode* root, int& maxVal)
{
if(root == nullptr) return 0;
int left = diameter(root->left, maxVal);
int right = diameter(root->right, maxVal);
int depth = max(left, right) +1;
maxVal = maxVal > (left + right) ? maxVal : (left + right);
return depth;
}
};
题四：leetcode：226（翻转二叉树）
(https://leetcode-cn.com/problems/invert-binary-tree/)
题目描述：
翻转一棵二叉树。
示例：
输入：
4
/
2 7
/ \ /
1 3 6 9
输出：
4
/
7 2
/ \ /
9 6 3 1
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root == nullptr) return root;
TreeNode* pLeft = root->left;
TreeNode* pRight = root->right;
root->left = invertTree(pRight);
root->right = invertTree(pLeft);
return root;
}
};
题五：leetcode：617（合并二叉树）
(https://leetcode-cn.com/problems/merge-two-binary-trees/)
题目描述：
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/
4 5
/ \ \
5 4 7
class Solution {
public:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if(t1 == nullptr && t2 == nullptr) return nullptr;
if(t1 == nullptr) return t2;
if(t2 == nullptr) return t1;
t1->val += t2->val;
t1->left = mergeTrees(t1->left, t2->left);
t1->right = mergeTrees(t1->right, t2->right);
return t1;
}
};
题六：leetcode：112（路径总和）
(https://leetcode-cn.com/problems/path-sum/)
题目描述：
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/
4 8
/ /
11 13 4
/ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
int tempSum = 0;
return hasPathSum(root, tempSum, sum);
}
bool hasPathSum(TreeNode* root, int&tempSum, int sum)
{
if(root == nullptr) return 0;
tempSum += root->val;
if(root->left == nullptr && root->right == nullptr)
{
return (tempSum == sum ? true : false);
}
if(true == hasPathSum(root->left, tempSum, sum)) return true;
tempSum -= (root->left == nullptr ? 0 : root->left->val);
if(true == hasPathSum(root->right, tempSum, sum)) return true;;
tempSum -= (root->right == nullptr ? 0 : root->right->val);
return false;
}
};
