/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
* 给定一个二叉树，找出其最大深度。
* 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
* 说明: 叶子节点是指没有子节点的节点。
* 示例：
* 给定二叉树 [3,9,20,null,null,15,7]，
* 3
* / \
* 9 20
* / \
* 15 7
* 返回它的最大深度 3 。
*/
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
/**
*1 递归的终止条件是给节点为空
*2 计算给节点的左右节点的最大深度
*/
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
/**
* Definition for a binary tree node.
* <p>
* 给出一个完全二叉树，求出该树的节点个数。
* 说明：
* 完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
* 示例:
* 输入:
* 1
* / \
* 2 3
* / \ /
* 4 5 6
* 输出: 6
*/
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
if (root.right == null && root.left == null) {
return 1;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
/**
*226. 翻转二叉树
* 示例：
*
* 输入：
*
* 4
* / \
* 2 7
* / \ / \
* 1 3 6 9
* 输出：
*
* 4
* / \
* 7 2
* / \ / \
* 9 6 3 1
*/
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
/**
* 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
* 说明: 叶子节点是指没有子节点的节点。
* 示例:
* 给定如下二叉树，以及目标和 sum = 22，
*
* 5
* / \
* 4 8
* / / \
* 11 13 4
* / \ \
* 7 2 1
* 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
*/
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null) {
return (sum - root.val) == 0;
}
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
}
