10. 二叉树的所有路径

/ \ 45

/\ 86

\ 7

我们看什么时候访问节点 8，maxDepth(节点 2)的时候访问， maxDepth(节点 4)的时候又会访问，如果节点层级更高，重复访问的次数更加频繁，剩下的节点6、节点 7 都是同理。每一个节点访问的次数

大概是 O(logK)(设当前节点在第 K 层)。那能不能把这个频率降到 O(1) 呢？

答案是肯定的，接下来我们来优化这个算法。

优化解法

var diameterOfBinaryTree = function(root) { let help = (node) => {

if(node == null) return 0;

let left = node.left ? help(node.left) + 1: 0;

let right = node.right ? help(node.right) + 1: 0;

let cur = left + right;

if(cur > max) max = cur;

// 这个返回的操作相当关键 return Math.max(left, right);

} let max = 0;

if(root == null) return 0;

help(root);

return max;

};

在这个过程中设置了一个max全局变量，深度优先遍历这棵树，每遍历完一个节点就更新max，并通过返回值的方式自底向上把当前节点左右子树的最大高度传给父函数使用，使得每个节点只需访问一次即

可。

现在提交我们优化后的代码，时间消耗明显降低。

10. 二叉树的所有路径

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

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

示例:

/\ 23

\ 5

输出: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

递归解法

利用 DFS(深度优先遍历) 的方式进行遍历。

/**

• @param {TreeNode} root
• @return {string[]}

*/ var binaryTreePaths = function(root) {

let path = [];

let res = [];

let dfs = (node) => { if(node == null) return;

path.push(node);

dfs(node.left);

dfs(node.right);

if(!node.left && !node.right)

res.push(path.map(item => item.val).join('->'));

// 注意每访问完一个节点记得把它从path中删除，达到回溯效果 path.pop();

} dfs(root);

return res;

};

非递归解法

接下来我们通过非递归的后序遍历的方式来实现一下, 顺便复习一下后序遍历的实现。

var binaryTreePaths = function(root) { if(root == null) return [];

let stack = [];

let p = root;

let set = new Set();

res = [];

while(stack.length || p) { while(p) {

stack.push(p);