LeetCode-Path Sum II

Love The Way You Lie 2022-08-06 14:10 2阅读 0赞

题目：

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:  
Given the below binary tree and  `sum = 22` ,

5
                 / \
                4   8
               /   / \
              11  13  4
             /  \      \
            7    2      1

return true, as there exist a root-to-leaf path `5->4->11->2` which sum is 22.

开始没看清题，root-to-leaf，最后必须是叶子节点！！！回溯法，上代码：

public boolean hasPathSum(TreeNode root, int sum) {
    		if (root == null) {
    			return false;
    		}
    		if (root.left == null && root.right == null) {
    			if (sum-root.val == 0)
    				return true;
    			return false;
    		}
    		sum -= root.val;
    		if (hasPathSum(root.left, sum))
    			return true;
    		if (hasPathSum(root.right, sum))
    			return true;
    		sum += root.val;
    		return false;
    	}

在精简一下代码：

public boolean hasPathSum(TreeNode root, int sum) {
            if (root == null) return false;
            else if (root.left == null && root.right == null && sum == root.val) return true;
            return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val);
        }

然后再看第二个，不仅需要判断是否有，还需要把全部的路径输出，明显是回溯法。

public List<List<Integer>> pathSum(TreeNode root, int sum) {
            List<List<Integer>> lists = new ArrayList<List<Integer>>();
            dfs(lists, new ArrayList<Integer>(), root, sum);
            return lists;
        }
        
        private void dfs(List<List<Integer>> lists, List<Integer> list, TreeNode root, int sum) {
        	if (root == null) return;
        	list.add(root.val);
        	if (root.left == null && root.right == null && root.val == sum) {
        		lists.add(new ArrayList<Integer>(list));
        		list.remove(list.size()-1);
        		return;
        	}
        	dfs(lists, list, root.left, sum-root.val);
        	dfs(lists, list, root.right, sum-root.val);
        	list.remove(list.size()-1); 
        }

private void dfs(List<List<Integer>> lists, List<Integer> list, TreeNode root, int sum) {
        	if (root == null) return;
        	list.add(root.val);
        	if (root.left == null && root.right == null && root.val == sum) {
        		lists.add(new ArrayList<Integer>(list));
        		return;
        	}
        	List<Integer> temp = new ArrayList<Integer>(list);
        	dfs(lists, list, root.left, sum-root.val);
        	dfs(lists, temp, root.right, sum-root.val);
        }

private void dfs(List<List<Integer>> lists, List<Integer> list, TreeNode root, int sum) {
        	sum -= root.val;
            list.add(root.val);
            if (root.left == null && root.right == null && sum == 0) {
                lists.add(new ArrayList<>(list));
                return;
            }
            if (root.left != null) {
                dfs(lists, list, root.left, sum);
                list.remove(list.size()-1);
            }
            if (root.right != null) {
                dfs(lists, list, root.right, sum);
                list.remove(list.size()-1);
            }
        }

可以细细体会一下，这几个dfs方法有什么不同。

如果要求每次的起点不一定是root呢？也就是起点也可以任意，终点也可以任意。找到符合sum的所以路径：

public void findSum(TreeNode root, int sum, List<Integer> buffer, int level) {
        	if (root == null) return;
        	int temp = sum;
        	buffer.add(root.val);
        	for (int i = level; i > -1; i--) {
        		temp -= buffer.get(i);
        		if (temp == 0) print(buffer, i, level);
        	}
        	
        	List<Integer> c1 = new ArrayList<Integer>(buffer);
        	List<Integer> c2 = new ArrayList<Integer>(buffer);
        	
        	findSum(root.left, sum, c1, level+1);
        	findSum(root.right, sum, c2, level+1);
        }
        
        private void print(List<Integer> buffer, int level, int i) {
        	for (int j = level; j <= i; j++) {
        		System.out.print(buffer.get(j)+" ");
        	}
        	System.out.println();
        }

其实方法基本是一样的，只不过这个每次都保存路径，从当前节点向上找，直到根节点。这里有个思维的变换，不在以root为起点找，而是以node为结束点找。