剑指offer|二叉树中和为某一值的路径

我会带着你远行 2022-04-24 15:48 135阅读 0赞

【题目描述】  
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

时间限制：1秒 空间限制：32768K 热度指数：343027

【解题思路】

1.  运用**前序遍历**递归解决。
2.  结合**路径**的概念：  
    到达叶结点时判断target和current是否相等，相等则加入结果集，否则弹出最后一个结点；  
    未到达叶结点时进行递归调用。
3.  注意加入路径时，要使用**new的方式**，因为add添加的是引用，不new的话最终list保存都是相同的（最后一个路径）。

public class Solution {
        
        ArrayList<ArrayList<Integer>> re = new ArrayList<>();
        ArrayList<Integer> arrayList = new ArrayList<>();
        // 20ms 9544K
        public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        
    
            int current = 0;
            if(root != null)
                FindPath(root, target, current);
            return re;
        }
        
        private void FindPath(TreeNode root, int target, int current) {
                
            arrayList.add(root.val);
            current += root.val;    
                
            if(root.left == null && root.right == null && current == target){
        
                //因为add添加的是引用，如果不new一个的话，最终list保存到的只是最后一个path
                re.add(new ArrayList(arrayList));
            }        
            if(root.left != null){
        
                FindPath(root.left, target, current);
            }        
            if(root.right != null){
        
                FindPath(root.right, target, current);
            }    
            //已到叶节点之后会跳过两个递归函数到这里，此时要把最后一个结点从路径中删除，才能返回上层结点    
            Integer val = arrayList.remove(arrayList.size()-1);
            current = current - val;        
        }
    }