数据结构与算法之二叉树: Leetcode 29. 路径总和 (Typescript版)网站首页 学无止境

数据结构与算法之二叉树: Leetcode 29. 路径总和 (Typescript版)

Wangs Blog 2024-07-01 11:59:07

简介数据结构与算法之二叉树: Leetcode 29. 路径总和 (Typescript版)

路径总和

https://leetcode.cn/problems/path-sum/

描述

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

示例1

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

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

示例2

  1
 / 
2   3

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例2

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

提示

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

算法实现

1 ）方案 1

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
    if(!root) return false
    let res = false;
    const dfs = (n: TreeNode | null, v: number) => {
        // 在叶子节点处符合题目要求, 则结束递归
        if (!n.left && !n.right && v === targetSum) {
            res = true;
            return;
        }
        n.left && dfs(n.left, v + n.left.val);
        n.right && dfs(n.right, v + n.right.val);
    }
    dfs(root, root.val)
    return res;
}

思路
- 深度优先遍历中，记录当前路径的节点值的和
- 在叶子节点处，判断当前路径的节点值的和是否等于目标值
步骤
- 深度优先遍历二叉树，在叶子节点处，判断当前路径的节点值的和是否等于目标值,是就返回true
- 遍历结束，如果没有匹配，就返回false

2 ）方案 2

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
    if (!root) {
        return false
	}
	function process(node: TreeNode, rest: number) {
		if (!node.left && !node.right) {
			return rest === node.val
		}
		let isSum = false
		if (node.left) {
			isSum ||= process(node.left, rest - node.val)
		}
		if (node.right) {
			isSum ||= process(node.right, rest - node.val)
		}
		return isSum
	}
  return process(root,targetSum)
};

这是官方示例，也是用的递归，深度优先遍历
这个只是换了一种累减的思路，同方案1的思路

3 ）方案 3

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
  if (!root) return false
  if(!root.left && !root.right) return root.val == targetSum;
  return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
};

这个是方案2的简洁版

4 ）方案 4

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
    if(!root) return false
    const q:[TreeNode | null, number][] = [[root, root.val]] // 声明一个队列
    while (q.length) {
      const first = q.shift() // 拿到当前队首元素
      const [n, v] = first
      if (!n.left && !n.right && v === targetSum) return true // 找到了节点
      if (n.left) q.push([n.left, v + n.left.val])
      if (n.right) q.push([n.right, v + n.right.val])
    }
    return false
}

这里是官方示例，是python的版本修改而来的
这个思想是基于广度优先遍历，使用队列保存遍历到每个节点时的路径和
如果该节点恰好是叶子节点，并且路径和正好等于sum，说明找到了解

5 ）方案 5

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
    if(!root) return false
    const stack:[TreeNode | null, number][] = [[root, root.val]] // 声明一个栈
    while (stack.length) {
      const first = stack.pop() // 拿到当前栈顶元素
      const [n, v] = first
      if (!n.left && !n.right && v === targetSum) return true // 找到了节点
      if (n.left) stack.push([n.left, v + n.left.val])
      if (n.right) stack.push([n.right, v + n.right.val])
    }
    return false
}