LeetCode 113. 路径总和 II

2020-05-12 16:05:19来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

LeetCode 113. 路径总和 II

我的LeetCode:https://leetcode-cn.com/u/ituring/

我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii

LeetCode 113. 路径总和 II

题目

给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明:?叶子节点是指没有子节点的节点。

示例:

给定如下二叉树,以及目标和?sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
返回:

[
   [5,4,11,2],
   [5,8,4,5]
]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/path-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

思路1-DFS/深度优先,注意叶子节点的处理

从根开始DFS即可,需要注意的是叶子节点的处理;

  • 当前节点为叶子节点的,停止递归;
  • 当前节点左右子节点有一个为null的,只递归处理非null节点;

这样做是为了避免叶子节点的两个null节点递归最终会出现两个重复的数据;

算法复杂度:

  • 时间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
  • 空间复杂度: $ {\color{Magenta}{\Omicron\left(logn\right)}} $ 除了结果所需外递归栈的深度

算法源码示例

package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ZhouJie
 * @date 2020年5月3日 下午5:26:02 
 * @Description: 113. 路径总和 II
 *
 */
public class LeetCode_0113 {

}

//  Definition for a binary tree node.
class TreeNode_0113 {
	int val;
	TreeNode_0113 left;
	TreeNode_0113 right;

	TreeNode_0113(int x) {
		val = x;
	}
}

class Solution_0113 {

	/**
	 * @author: ZhouJie
	 * @date: 2020年5月3日 下午5:27:56 
	 * @param: @param root
	 * @param: @param sum
	 * @param: @return
	 * @return: List<List<Integer>>
	 * @Description: 1-从根递归/DFS,注意最后叶子节点的处理;
	 *
	 */
	private List<List<Integer>> all = new ArrayList<List<Integer>>();

	public List<List<Integer>> pathSum(TreeNode_0113 root, int sum) {
		if (root == null) {
			return all;
		}
		searchAllPath(root, 0, new ArrayList<Integer>(), sum);
		return all;
	}

	private void searchAllPath(TreeNode_0113 root, int add, List<Integer> list, int sum) {
		if (root == null) {
			if (add == sum && list.size() > 0) {
				all.add(list);
			}
		} else {
			add += root.val;
			list.add(root.val);
			TreeNode_0113 left = root.left;
			TreeNode_0113 right = root.right;
			// 最后的子节点需要判断,否则会出现重复值,-若叶子节点无左右子节点,直接左右递归就会产生两个相同的路径list;
			// 递归时list需要新建并加入当前路径已有的值,因为路径是唯一的,list不能继续复用;
			if (left == null && right == null) {
				searchAllPath(null, add, new ArrayList<>(list), sum);
			} else {
				if (left != null) {
					searchAllPath(left, add, new ArrayList<>(list), sum);
				}
				if (right != null) {
					searchAllPath(right, add, new ArrayList<>(list), sum);
				}
			}
		}
	}
}


原文链接:https://www.cnblogs.com/izhoujie/p/12875904.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:求求你了,不要再自己实现这些逻辑了,开源工具类不香吗?

下一篇:Java Stream 流如何进行合并操作