剑指offer Binary Tree Depth-First Search

剑指offer-二叉树中和为某一值的路径

Posted by franki on May 6, 2021

二叉树中和为某一值的路径

输入一颗二叉树和一个整数，打印出二叉树中的节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

思路

1 利用深度优先遍历，记录经过的路径，当遍历到叶子节点时，查看当前的路径和与目标值是否相等，若相等，那么说明找到了；若不相等，那么说明不符合；需要回退，继续查找

2 重复1的过程，即可找到所有符合的路径

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} target
 * @return {number[][]}
 */
var pathSum = function(root, target) {
    const res = [];
    const curSum = 0;
    const path = [];
    dfs(root, target, curSum, path, res);
    return res;
};

function dfs(root, target, curSum, path, res) {
    if (root === null) {
        return null;
    }
    curSum += root.val;
    path.push(root.val);

    const isLeaf = root.left === null && root.right === null;
    if (curSum === target && isLeaf) {
        res.push([...path]);
    }

    dfs(root.left, target, curSum, path, res);
    dfs(root.right, target, curSum, path, res);

    path.pop();
}

复杂度分析

  • 时间复杂度: O(N)
  • 空间复杂度: O(N)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG
    FRIENDS