一天一大 lee(二叉树的所有路径)难度:简单-Day20200904

题目:

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输入: 1 / \ 2 3 \ 5 输出: ["1->2->5", "1->3"] 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

抛砖引玉

深度优先搜索（DFS）

从根节点开始递归遍历

递归传入的节点为： null，递归结束存在 val，则拼接存在左右节点则递归遍历左右记得点，并且传入已拼接的字符给后续递归继续拼接左右节点为 null 则遇到叶子节点，将拼接的字符存入结果数组 /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {string[]} */ var binaryTreePaths = function (root) { let _result = [] function dfs(node, path) { if (!node) return path += node.val.toString() if (node.left === null && node.right === null) { // 当前节点是叶子节点 _result.push(path) // 把路径加入到答案中 } else { path += '->' // 当前节点不是叶子节点，继续递归遍历 dfs(node.left, path) dfs(node.right, path) } } dfs(root, '') return _result }

广度优先搜索（BFS）

node_queue 存放待处理节点path_queue 存在过程中拼接的字符 var binaryTreePaths = function (root) { let _result = [] if (root === null) return _result let node_queue = [root], path_queue = [root.val.toString()] while (node_queue.length) { let node = node_queue.shift(), path = path_queue.shift() if (node.left === null && node.right === null) { _result.push(path) } else { if (node.left !== null) { node_queue.push(node.left) path_queue.push(path + '->' + node.left.val.toString()) } if (node.right !== null) { node_queue.push(node.right) path_queue.push(path + '->' + node.right.val.toString()) } } } return _result }

博客: 小书童博客

每天的每日一题，写的题解会同步更新到公众号一天一大 lee 栏目 欢迎关注留言

公号: 坑人的小书童