134，路徑總和

給定一個二叉樹和一個目标和，判斷該樹中是否存在根節點到葉子節點的路徑，這條路徑上所有節點值相加等于目标和。

說明: 葉子節點是指沒有子節點的節點。

示例: 

給定如下二叉樹，以及目标和 

sum = 22

，

1          5
2         / \
3        4   8
4       /   / \
5      11  13  4
6     /  \      \
7    7    2      1
           

傳回 

true

, 因為存在目标和為 22 的根節點到葉子節點的路徑 

5->4->11->2

。

上期的問題是：133，二叉樹的最小深度

1public int minDepth(TreeNode root) {
2    if (root == null) return 0;
3    int left = minDepth(root.left);
4    int right = minDepth(root.right);
5    return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1;
6}
           

解析：

1public int minDepth(TreeNode root) {
2    if (root == null)
3        return 0;
4    if (root.left != null && root.right != null)
5        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
6    return Math.max(minDepth(root.left), minDepth(root.right)) + 1;
7}
           

1public int minDepth(TreeNode root) {
 2    if (root == null) return 0;
 3    Queue<TreeNode> Q = new LinkedList<>();
 4    Q.add(root);
 5    int i = 0;
 6    while (!Q.isEmpty()) {
 7        i++;
 8        int k = Q.size();
 9        for (int j = 0; j < k; j++) {
10            TreeNode rt = Q.peek();
11            if (rt.left != null) Q.add(rt.left);
12            if (rt.right != null) Q.add(rt.right);
13            Q.poll();
14            if (rt.left == null && rt.right == null) return i;
15        }
16    }
17    return -1;
18}