【算法】二叉树的所有路径和递归思想

vlambda
2022-04-23

【算法】二叉树的所有路径和递归思想

今天是力扣简单算法第7题，往期链接如下：

题目来源

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-tree-paths/

给你一个二叉树的根节点 root ，按任意顺序，返回所有从根节点到叶子节点的路径。叶子节点是指没有子节点的节点。

分析题目

牵涉知识点如下

二叉树

二叉树是树类的一种数据结构，二叉树的每个节点最多只能包含两个子节点，每个子节点下有可能分0,1，2个子节点

节点的val值

节点的val值返回对应的节点

递归

就是函数自己调用自己。

例如：斐波拉契数列，1,1,2,3,5,8,13,21,34,55...求第 n 项

function fib(n) { if (n === 1 || n === 2) return n - 1 return fib(n - 1) + fib(n - 2)}console.log(fib(10)) // 3

求 1-100 的和

function sum(n) { if (n == 1) return 1 return sum(n - 1) + n}

...扩展运算符

扩展运算符，三个点（...）表示

可以在函数调用/数组构造时, 将数组表达式或者string在语法层面展开；

往期文章链接如下：

Array.prototype.join()

根据分隔符把数组分割成字符串

let words = ["Hello", "Alaska", "Dad", "Peace"] console.log(words.join('->')) // Hello->Alaska->Dad->Peace

解题

综上分析：我们定义一个递归函数dfs，首先把根节点值传到数组里，如果左节点存在，把左节点作为循环节点，如果有节点存在，把右节点作为循环阶段，当左右节点不存在时，保存结果。

/** * 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 * @return {string[]} */var binaryTreePaths = function(root) { let result = [] function dfs(p,arr){ arr.push(p.val) if(!p.left && !p.right){ result.push(arr.join('->')) } if(p.left){ dfs(p.left,[...arr]) } if(p.right){ dfs(p.right, [...arr]) } } dfs(root,[]) return result};