二叉树路径问题题目

某一个节点(不一定是根节点)，从上向下寻找路径，到某一个节点(不一定是叶节点)结束，采用 dfs 解决

一般路径 模板

const res = []
const dfs = (root, path) => {
	if (!root) return // 根节点为空直接返回
	path.push(root.val) // 做出选择
	if (!root.left && !root.right) { // 如果到叶节点
		res.push([...path])
		return
	}
    //继续递归
	dfs(root.left, path)
	dfs(root.right, path)
	path.pop() // 撤销选择
}

给定和路径 模板

const res = []
const dfs = (root, sum, path) => {
	if (!root) return // 根节点为空直接返回

	// 做出选择
	sum -= root.val
	path.push(root.val)

	if (!root.left && !root.right && sum === 0) { // 如果到叶节点
		res.push([...path])
		return
	}
	//继续递归
	dfs(root.left, sum, path)
	dfs(root.right,sum, path)
	// 撤销选择
	path.pop()
}

257. 二叉树的所有路径

这里注意 -> 放在递归中，其他的就是一般路径模板

function binaryTreePaths(root: TreeNode | null): string[] {
    const res: string[] = []
    const dfs = (root: TreeNode, s: string) => {
        if (!root) return
        s += root.val
        if (!root.left && !root.right) {
            return res.push(s)
        }
        dfs(root.left, s + '->')
        dfs(root.right, s + '->')
    }
    dfs(root, '')
    return res
};

113. 路径总和 II

直接给定和路径模板

function pathSum(root: TreeNode | null, targetSum: number): number[][] {
    const res: number[][] = []
    const dfs = (root: TreeNode, sum: number, s: string) => {
        if (!root) return
        sum -= root.val
        s += root.val
        if (!root.left && !root.right && sum === 0) {
            return res.push(s.split('#').map((i) => Number(i)))
        }
        dfs(root.left, sum, s + '#')
        dfs(root.right, sum, s + '#')
    }
    dfs(root, targetSum, '')
    return res
};

437. 路径总和 III

给定和路径模板

1. 不是跟节点开始的，都需要双重递归
2. 不需要在叶子节点结束，因为可能为 0，或负数，所以达到给定和后，不需要 return，继续向下递归

function pathSum(root: TreeNode | null, targetSum: number): number {
    let res = 0

    const dfs = (root: TreeNode) => {
        if (!root) return
        dfs2(root, targetSum)
        dfs(root.left)
        dfs(root.right)
    }

    const dfs2 = (root: TreeNode, sum: number) => {
        if (!root) return
        sum -= root.val
        if (sum === 0) res++
        dfs2(root.left, sum)
        dfs2(root.right, sum)
    }
    dfs(root)

    return res
};

988. 从叶结点开始的最小字符串

换汤不换药，套用一般路径模板

function smallestFromLeaf(root: TreeNode | null): string {
    const res: string[] = []
    const dfs = (root: TreeNode, s: string) => {
        if (!root) return
        s += String.fromCharCode(97 + root.val)
        if (!root.left && !root.right) {
            return res.push([...s].reverse().join(''))
        }
        dfs(root.left, s)
        dfs(root.right, s)
    }
    dfs(root, '')
    return res.sort()[0]
};