題目描述

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

解法1 遞歸

官方給的解答，非常清晰簡明。

/**
 * Definition for a binary tree node.
 * public 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;
    //順著節(jié)點下去，sum值要減去選取的節(jié)點的值
    sum -= root.val;
    //如果給的只有一個根節(jié)點，此時sum應(yīng)該為0
    if ((root.left == null) && (root.right == null))
      return (sum == 0);
    return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
  }
}

解法2 迭代

從根節(jié)點開始sum隨路徑向下減去相應(yīng)的節(jié)點值，到達葉子結(jié)點時判斷sum是否為0，是返回true，不是則去另一個葉子節(jié)點的路徑。
不能單純的在路徑上每經(jīng)過一個節(jié)點判斷sum是否為0，因為sum在到達葉子節(jié)點的途中有可能會減為0，此時不能返回true。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        //申請兩個棧，一個用來存節(jié)點，一個用來存sum隨節(jié)點的變動
        LinkedList<TreeNode> stack1 = new LinkedList<>();
        LinkedList<Integer> stack2 = new LinkedList<>();
        TreeNode curr = root;
        while (!stack1.isEmpty() || curr != null) {
            //從最左邊的葉子節(jié)點開始，跳出while時，curr = null
            while (curr != null) {
                sum -= curr.val;
                stack1.push(curr);
                stack2.push(sum);
                curr = curr.left;
            }
            //curr此時為葉子節(jié)點
            curr = stack1.pop();
            //必須是葉子節(jié)點才算，要滿足這個節(jié)點左右孩子為null并且sum此時等于0
            if (sum == 0 && curr.left == null && curr.right == null) {
                return true;
            }
            sum = stack2.pop();
            curr = curr.right;
        }
        return false;
    }
}

題目描述

給定一個二叉樹和一個目標和，找到所有從根節(jié)點到葉子節(jié)點路徑總和等于給定目標和的路徑。
113. 路徑總和Ⅱ

解法1 遞歸

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> list = new LinkedList<>();
        LinkedList<Integer> res = new LinkedList<>();
        pathSum(list, res, root, sum);
        return list;
    }

    public void pathSum(List<List<Integer>> list, LinkedList<Integer> res, TreeNode root, int sum){
        if(root == null){
            return;
        }
        res.add(root.val);
        if(root.val == sum && root.left == null && root.right == null){
            list.add(new ArrayList<>(res));
        }else{
            pathSum(list, res, root.left, sum - root.val);
            pathSum(list, res, root.right, sum - root.val);
        }
        //回溯
        res.removeLast();
    }
}

題目描述

給定一個二叉樹，返回所有從根節(jié)點到葉子節(jié)點的路徑。
257. 二叉樹的所有路徑

解法1 遞歸

最想想到遞歸。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        helper(root,"",res);
        return res;
    }
    //res用來存儲所有路徑，path用來存放遍歷到的路徑
    public void helper(TreeNode root, String path, List<String> res){
        //root為null，直接跳出函數(shù)，返回的res為空
        if(root != null){
            path += Integer.toString(root.val);
            //找到了根節(jié)點，將路徑存入res中
            if(root.left == null && root.right == null){
                res.add(path);
                root = null;
            }else{
                //不是根節(jié)點，添加"->"并繼續(xù)遍歷
                path += "->";
                helper(root.left,path,res);
                helper(root.right,path,res);
            }
        }
    }
}

題目描述

給出一棵二叉樹，其上每個結(jié)點的值都是 0 或 1 。每一條從根到葉的路徑都代表一個從最高有效位開始的二進制數(shù)。例如，如果路徑為 0 -> 1 -> 1 -> 0 -> 1，那么它表示二進制數(shù) 01101，也就是 13 。

對樹上的每一片葉子，我們都要找出從根到該葉子的路徑所表示的數(shù)字。
1022. 從根到葉的二叉樹進制數(shù)之和

解法1

也可以用上面題的方法求出所有路徑，再進行二進制數(shù)之和的計算。這里使用遞歸，邊累加邊遍歷。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int sumRootToLeaf(TreeNode root) {
        return helper(root,0);
    }

     private int helper(TreeNode root, int sum){
        if(root == null) return 0;
        //sum等于從根節(jié)點到當前節(jié)點的二進制數(shù)的十進制表示
        sum = 2 *sum + root.val;
        //遇到葉子節(jié)點，返回sum，代表(又)一條路徑的二進制數(shù)被累加
        if(root.left == null && root.right == null){
            return sum;
        }
        //沒到葉子節(jié)點，繼續(xù)遍歷
        return helper(root.left, sum) + helper(root.right, sum);
    }
}