翻转二叉树

翻转一棵二叉树。

示例:

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)
}