翻转二叉树

翻转一棵二叉树。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入：
     4
   /   \
  2     7
 / \   / \
1   3 6   9
输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

解题思路&题解

利用递归，将左子树和右子树交换。代码如下：

1
2
3
4
5
6
7
8
9
func invertTree(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	left := invertTree(root.Right)
	root.Right = invertTree(root.Left)
	root.Left = left
	return root
}

路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。

示例 1：

1
2
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true

示例 2：

1
2
输入：root = [1,2,3], targetSum = 5
输出：false

示例 3：

1
2
输入：root = [1,2], targetSum = 0
输出：false

提示：

  • 树中节点的数目在范围 [0, 5000] 内
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

解题思路&题解

这题和之前的求两数和差不多思路，将已遍历的节点值放入haspMap中，并且每次访问节点的时候，计算当前节点和目标数相减后的值是否存在hashMap中。
具体思路如下

  1. 读取当前节点的值
  2. 将当前节点的值放入hashMap中
  3. 判断 targetSum - 当前节点的值 是否在hashMap中
  4. 在则返回true,不在则继续遍历
1
2
3
4
5
6
7
8
9
10
11
func hasPathSum(root *TreeNode, targetSum int) bool {
	if root == nil {
		return false
	}

	if root.Left == nil && root.Right == nil {
		return targetSum == root.Val
	}

	return hasPathSum(root.Left, targetSum-root.Val) || hasPathSum(root.Right, targetSum-root.Val)
}