【LeetCode算法修炼指南】——112.路径总和、113.路径总和II

112.路径总和

原题链接
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

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

示例:
给定如下二叉树，以及目标和 sum = 22，

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

要点

叶子节点的性质:左右节点均为空。
在遍历的过程中将已经遍历的数值减去且在叶子节点的时候恰好为0则成立。

递归

先序遍历，子树的剩余的目标和 = 目标和-当前结点值

代码片段

func hasPathSum(root *TreeNode, sum int) bool {
	if root == nil {
		return false
	}
	tmp := root.Val

	if sum-tmp == 0 && root.Left == nil && root.Right == nil {
		return true
	}

	return hasPathSum(root.Left, sum-tmp) || hasPathSum(root.Right, sum-tmp)
}

代码解释

1. 只要求某一个分支成立，则运算结果为True
2. 这一题仅仅实在先序遍历的过程中，增加了一个判断和的条件

---

DFS(深度优先遍历)

代码片段

func hasPathSum2(root *TreeNode, sum int) bool {
	if root == nil {
		return false
	}
	link := list.New()
	type tmp struct {
		node *TreeNode
		val  int
	}
	link.PushBack(tmp{node: root, val: sum - root.Val})

	for link.Len() > 0 {
		node := link.Remove(link.Back()).(tmp)
		if node.val == 0 && node.node.Left == nil && node.node.Right == nil {
			return true
		}

		if node.node.Left != nil {
			link.PushBack(tmp{node: node.node.Left, val: node.val - node.node.Left.Val})
		}
		if node.node.Right != nil {
			link.PushBack(tmp{node: node.node.Right, val: node.val - node.node.Right.Val})
		}
	}

	return false
}

代码解释

其实这里无论用DFS还是BFS都是可以解决问题的。

---

113.路径总和II

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

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

示例:
给定如下二叉树，以及目标和 sum = 22，

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

要点

1. 这一题是112.路径总和的扩展，在原先的基础上增加了记录。
2. 在整个递归的过程中记录当前遍历的数组，当符合条件的时候将数组添加到结果数组当中。

递归

代码片段

func pathSumHelper(root *TreeNode, sum int, _list *[][]int, inner []int) {
	if root == nil {
		return
	}
	sum -= root.Val
	inner = append(inner, root.Val)
	if root.Left == nil && root.Right == nil {
		if sum == 0 {
			innerTmp := append([]int{}, inner...)//拷贝数组，否则存放引用的话后序数组内容可能变更。
			*_list = append(*_list, innerTmp)
		}
	}
	if root.Left != nil {
		pathSumHelper(root.Left, sum,_list,inner)
	}
	if root.Right != nil {
		pathSumHelper(root.Right,sum,_list,inner)
	}
	inner = inner[:len(inner)-1]
	return
}
func pathSum(root *TreeNode, sum int) [][]int {
	var _list = [][]int{}
	var ineer = []int{}
	pathSumHelper(root, sum, &_list, ineer)
	return _list
}

代码解释

_list是结果数组存放返回的结果。
inner是记录当前遍历中数组的元素，递归过程会记录当前层级的数组状态(指向新的地址)，并不会一直往inner里面填充整棵树。

DFS(深度优先)

代码片段

func pathSum(root *TreeNode, sum int) [][]int {
	if root == nil {
		return nil
	}
	var nums [][]int
	link := list.New()
	type tmp struct {
		node *TreeNode
		val  int
		INT  []int
	}
	link.PushBack(tmp{node: root, val: sum - root.Val, INT: []int{root.Val}})
	for link.Len() > 0 {
		node := link.Remove(link.Back()).(tmp)
		if node.val == 0 && node.node.Left == nil && node.node.Right == nil {
			nums = append(nums, node.INT)
		} else if node.val != 0 && node.node.Left == nil && node.node.Right == nil {
			continue
		}
		if node.node.Right != nil {
			rightINT := append([]int{}, node.INT...)//拷贝数组性能差
			rightINT = append(rightINT, node.node.Right.Val)
			link.PushBack(tmp{node: node.node.Right, val: node.val - node.node.Right.Val, INT: rightINT})
		}
		if node.node.Left != nil {
			rightINT := append([]int{}, node.INT...)//拷贝数组性能差
			rightINT = append(rightINT, node.node.Left.Val)
			link.PushBack(tmp{node: node.node.Left, val: node.val - node.node.Left.Val, INT: rightINT})
		}
	}
	return nums
}

代码解释

创建一个tmp结果模拟递归过程中数组的状态。

---

????????????制作动画过程不易，请大家顺手点赞收藏咯 谢谢~???????????? 有其它题目不理解的也可以一起学习，如有错误欢迎指出~