剑指offer算法题


树

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

题目分析
对树进行深度优先遍历，每到一个节点用target-当前节点的值。当到达了叶子节点，如果target的值正好为0，证明这条路径符合条件，加入listAll中；如果不符合条件，则list.remove()退回上一层的节点。

下面是Java代码

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>> listAll = new ArrayList<ArrayList<Integer>>();
    private ArrayList<Integer> list = new ArrayList<>();
    
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) { 
        if(root == null){ 
            return listAll;
        }
        
        list.add(root.val);
        target -=root.val;
        if(target == 0 && root.left == null && root.right == null){ 
            listAll.add(new ArrayList<Integer>(list));
        }
        if(root.left!=null){ 
            FindPath(root.left,target);
        }
        if(root.right !=null){ 
            FindPath(root.right,target);
        }
		/* list.remove()的作用： 假设当前是10,5,12,4,7这种情况，递归到10,5,4的时 候没有发现2，2的点，这时候就要把4去掉，再加入7才对， 不然就会结果中变成10,5,4,7，这个4就是一个没去掉的 叶子节点。 */


        list.remove(list.size()-1);
        return listAll;
    }
}

参考https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?tpId=13&&tqId=11177&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

声明：本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。