剑指Offer-二叉树中和为某一值的路径

痛定思痛。 2022-02-25 08:44 113阅读 0赞

## 题目描述 ##

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

精简解题思路：这题推荐使用**递归**！要形成路径，会想到使用**深度优先搜索**，在队列中加入节点后，先判断一下target值有没有满足，若不满足，继续递归左右子树，若递归到某一叶节点，当前节点的值加入不满足target，则队列要**退回当前节点**。如果题目中没有要求注意事项，这个代码堪称完美！（测试用例太少，代码还是能AC的。）但是最后还是忽略了返回的list中，数组长度大的数组靠前。如果要加上判断数组长度，就不能将递归写在主函数中了，需要拆分下来。  
最优解：数组长度排序，可以使用**Collections.sort**方法，Collections是一个工具类，sort是其中的静态方法，是用来对List类型进行排序的。但默认是正序，如果要实现逆序，需要**重写Comparator接口的compare方法**来完成自定义排序。

> 注：compare返回的int值有三种类型，compare(对象1, 对象2)  
> 负整数：对象1排在前  
> 0：位置不变  
> 正整数：对象1排在后

## 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>> result = new ArrayList<>();
        private ArrayList<Integer> list = new ArrayList<>();
        public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
            if(root==null || root.val>target)
                return result;
            list.add(root.val);
            target -=root.val;
            if(target==0 && root.left==null && root.right==null)
                result.add(new ArrayList<Integer>(list));
            if(root.left!=null) FindPath(root.left, target);
            if(root.right!=null) FindPath(root.right, target);
            list.remove(list.size()-1);
            return result;
        }
    }

## 最优解—包含数组排序 ##

import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Comparator;
    public class Solution {
        private ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        private ArrayList<Integer> list = new ArrayList<>();
        public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
            GetPath(root, target);
            Collections.sort(result, new Comparator<ArrayList<Integer>>() {
                @Override
                public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
                    if(o1.size()<o2.size())
                        return 1;
                    else
                        return -1;
                }
            });
            return result;
        }
        
        public void GetPath(TreeNode root,int target) {
            if(root==null || root.val>target)
                return;
            list.add(root.val);
            target -=root.val;
            if(target==0 && root.left==null && root.right==null)
                result.add(new ArrayList<Integer>(list));
            if(root.left!=null) GetPath(root.left, target);
            if(root.right!=null) GetPath(root.right, target);
            list.remove(list.size()-1);
        }
    }