积分商城平台_网页浏览器软件有哪些_恢复原来的百度_嘉兴网站建设

leetcode 257

思路

利用递归+回溯来获取二叉树的所有路径，回溯是每次遍历到叶子节点以后可以回退回去，然后继续进行遍历，比如把左节点遍历以后要回退到根节点，然后遍历右节点
我们我们遍历过程中需要一个path来存每一条路径中的节点值，用result来存总结果值
我们每次遍历到当前节点的时候把当前节点的值放入path中，然后看是否到达了叶子节点(左右子树都为空)，如果到了叶子节点就结束递归，此时path就是这条路径，放入到result中
如果没有到叶子节点的话，那就递归左节点和右节点，由于要回退，所以每次递归完成后，我们要回到上一级看另外一侧的分支，所以有个出栈的操作

模拟一下题目中示例1的过程

初始化：result = [], path = []

1. 递归：deep(1, path,result)
   path = [1]，存在左右节点
2. 左子树递归：deep(2, [1], [])
   path = [1, 2]，存在右节点
3. 递归右节点：deep(5, [1,2], [])
   path = [1, 2, 5]，没有左右节点->当前节点是叶子节点
   result = [‘1->2->5’]，退出本次递归, 第三次递归结束
   path.pop -> path = [1,2], 右节点递归完成，退出第二次递归
   path = [1]，根节点左节点递归完成，继续右节点递归
4. 递归根节点的右节点：deep(3, [1], [‘1->2->5’])
   path = [1,3]，没有左右节点->当前节点是叶子节点
   reuslt = [‘1->2->5’,‘1->3’]
5. 递归完成 return result;

实现

var binaryTreePaths = function (root) {if (!root) return [];const result = [], path = []// path：单路径const deep = (node, path, result) => {path.push(node.val)if (!node.left && !node.right) {result.push(path.join('->'))return;}if (node.left) {deep(node.left, path, result)path.pop()}if (node.right) {deep(node.right, path, result)path.pop()}}deep(root, path, result)return result
};