剑指 Offer 34. 二叉树中和为某一值的路径（113. 路径总和 II）

标签：node TreeNode val Offer 路径 二叉树 new root 节点

题目：

 

思路：

【1】采用深度遍历的方式

【2】采用广度遍历的方式

代码展示：

采用广度遍历的方式：

//时间3 ms击败6.94%
//内存41.7 MB击败74.94%
//时间复杂度：O(N^2)，其中 N 是树的节点数。
//空间复杂度：O(N)，其中 N 是树的节点数。空间复杂度主要取决于哈希表和队列空间的开销，哈希表需要存储除根节点外的每个节点的父节点，队列中的元素个数不会超过树的节点数。
class Solution {
    List<List<Integer>> ret = new LinkedList<List<Integer>>();
    Map<TreeNode, TreeNode> map = new HashMap<TreeNode, TreeNode>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null) return ret;

        Queue<TreeNode> queueNode = new LinkedList<TreeNode>();
        Queue<Integer> queueSum = new LinkedList<Integer>();
        queueNode.offer(root);
        queueSum.offer(0);

        while (!queueNode.isEmpty()) {
            TreeNode node = queueNode.poll();
            int rec = queueSum.poll() + node.val;

            if (node.left == null && node.right == null) {
                if (rec == targetSum) {
                    getPath(node);
                }
            } else {
                if (node.left != null) {
                    map.put(node.left, node);
                    queueNode.offer(node.left);
                    queueSum.offer(rec);
                }
                if (node.right != null) {
                    map.put(node.right, node);
                    queueNode.offer(node.right);
                    queueSum.offer(rec);
                }
            }
        }

        return ret;
    }
    
    public void getPath(TreeNode node) {
        List<Integer> temp = new LinkedList<Integer>();
        while (node != null) {
            temp.add(node.val);
            node = map.get(node);
        }
        Collections.reverse(temp);
        ret.add(new LinkedList<Integer>(temp));
    }
}

 

采用深度遍历的方式：

//时间1 ms击败99.95%
//内存41.7 MB击败63.45%
//时间复杂度：O(N^2)，其中 N 是树的节点数。在最坏情况下，树的上半部分为链状，下半部分为完全二叉树，并且从根节点到每一个叶子节点的路径都符合题目要求。
//此时，路径的数目为 O(N)，并且每一条路径的节点个数也为 O(N)，因此要将这些路径全部添加进答案中，时间复杂度为 O(N^2)。
//空间复杂度：O(N)，其中 N 是树的节点数。
//空间复杂度主要取决于栈空间的开销，栈中的元素个数不会超过树的节点数。
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, 0, targetSum);
        return res;
    }
    //这里采用加法而不用减法的原因是对于每个节点我们都必须先判断不为null才能拿来用，不然是会报错的
    public void dfs(TreeNode root, int num, int sum){
        if(root == null) return;
        num += root.val;
        list.add(root.val);
        //其次，这里采用等号的原因是，由于节点的值为-1000 <= Node.val <= 1000，故是必须遍历到叶子节点才能停，不然提前结束的逻辑是不对的
        //而且这里的new一格新数组是因为JAVA中数组是引用类型
        if(num == sum && root.left == null && root.right == null) res.add(new ArrayList(list));
        dfs(root.left, num, sum);
        dfs(root.right, num, sum);
        //最后这里的-1是为了对数组的调整，根据深度遍历如树【1,2,3,4,5,6,7】，目标为8
        //那么首先是会遍历1,2,4这条路，这是递归的原则，那么此时数组里面的这三个数其实4是不要的，移除4相当于退回一格
        //那么再遍历右节点，就会有1,2,5.刚好满足
        list.remove(list.size() - 1);
    }
}

 

标签：node,TreeNode,val,Offer,路径,二叉树,new,root,节点
From： https://www.cnblogs.com/chafry/p/17159101.html