【剑指Offer】34. 二叉树中和为某一值的路径

不念不忘少年蓝@ 2022-11-27 15:38 136阅读 0赞

[NowCoder][]

## 题目描述 ##

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

下图的二叉树有两条和为 22 的路径：10, 5, 7 和 10, 12  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2OTY4MA_size_16_color_FFFFFF_t_70_pic_center]

import java.util.ArrayList;
    /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    public class Solution { 
    
        private ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        
        public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) { 
            backtracking(root, target, new ArrayList<Integer>());
            return ret;
        }
        
        // 等值的路径和
        private void backtracking(TreeNode root, int target, ArrayList<Integer> path) { 
            if(root == null)
                return;
            target -= root.val;
            path.add(root.val);
            
            if(target==0 && root.left == null && root.right == null)
                ret.add(new ArrayList<>(path));
            else { 
                backtracking(root.left, target, path);
                backtracking(root.right, target, path);
            }
            path.remove(path.size()-1);
        }
    }

[NowCoder]: https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?tpId=13&tqId=11177&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=bennyrhys@163.com
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2OTY4MA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/dcecb6b5e82c4fe8ba6e30e96e99bfa4.png