題目

輸入一棵二叉樹和一個整數(shù)，打印出二叉樹中結(jié)點值的和為輸入整數(shù)的所有路徑。
路徑定義為從樹的根結(jié)點開始往下一直到葉結(jié)點所經(jīng)過的結(jié)點形成一條路徑。

思路

使用前序遍歷，并統(tǒng)計當(dāng)前路徑的sum。
當(dāng)某個節(jié)點已經(jīng)不在路徑內(nèi)，需要回溯，將這個節(jié)點出棧，并從sum中減去對應(yīng)的值。

實現(xiàn)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
        List<List<Integer>> res = new ArrayList<>();

        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            List<Integer> path = new ArrayList<>();
            dfs(root, sum, path);
            return res;
        }
        
        public void dfs(TreeNode root, int sum, List<Integer> path){
            
            if(root==null) return;

            path.add(root.val);
            
            if(root.left==null && root.right==null )
                if(root.val==sum)
                    res.add(new ArrayList<Integer>(path));
            
            if(root.left!=null) 
                dfs(root.left,sum-root.val,path);
            
            if(root.right!=null) 
                dfs(root.right,sum-root.val,path);
            
            path.remove(path.size()-1);
            
        }
}