9. 二叉树的直径

二叉搜索树作为一种特殊的二叉树，当然是可以用上述的两种方式来实现的。

不过借助二叉搜索树有序的特性，我们也可以写出另外一个版本的深度优化遍历。

/**

• @param {TreeNode} root
• @param {TreeNode} p
• @param {TreeNode} q
• @return {TreeNode}

*/ var lowestCommonAncestor = function(root, p, q) {

if(root == null || root == p || root == q) return root;

// root.val 比 p 和 q 都大，找左孩子 if(root.val > p.val && root.val > q.val)

return lowestCommonAncestor(root.left, p, q);

// root.val 比 p 和 q 都小，找右孩子 if(root.val < p.val && root.val < q.val)

return lowestCommonAncestor(root.right, p, q);

else return root;

};

同时也可以采用非递归的方式:

var lowestCommonAncestor = function(root, p, q) { let node = root;

while(node) { if(p.val > node.val && q.val > node.val)

node = node.right;

else if(p.val < node.val && q.val < node.val)

node = node.left;

else return node;

} };

是不是被二叉树精简而优雅的代码惊艳到了呢？希望你能好好体会其中遍历的过程，然后务必自己独立实现一遍，保证对这种数据结构足够熟悉，增强自己的编程内力。

9. 二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

示例 : 给定二叉树

/ \

/ \

思路

所谓的求直径, 本质上是求树中节点左右子树高度和的最大值。

注意，这里我说的是树中节点, 并非根节点。因为会有这样一种情况:

1 /

2 / \

45 /\

86 \

7

那这个时候，直径最大的路径是: 8 -> 4 -> 2-> 5 -> 6 -> 7。交界的元素并不是根节点。这是这个问题特别需要注意的地方，不然无解。

初步求解

目标已经确定了，求树中节点左右子树高度和的最大值。开干！

/**

• @param {TreeNode} root
• @return {number}

*/ var diameterOfBinaryTree = function(root) {

// 求最大深度 let maxDepth = (node) => {

if(node == null) return 0;

return Math.max(maxDepth(node.left) + 1, maxDepth(node.right) + 1);

} let help = (node) => {

if(node == null) return 0;

let rootSum = maxDepth(node.left) + maxDepth(node.right);

let childSum = Math.max(help(node.left), help(node.right));

return Math.max(rootSum, childSum);

} if(root == null) return 0;

return help(root);

};

这样一段代码放到 LeetCode 是可以通过，但时间上却不让人很满意，为什么呢？

因为在反复调用 maxDepth 的过程，对树中的一些节点增加了很多不必要的访问。比如：