这个系列没啥花头，就是纯 leetcode 题目拆解分析，不求用骚气的一行或者小众取巧解法，而是用清晰的代码和足够简单的思路帮你理清题意。让你在面试中再也不怕算法笔试。

93. 完全二叉树的节点个数 (count-complete-tree-nodes)

题目

这里不贴题了，leetcode打开就行，题目大意：

给你一棵完全二叉树的根节点 root ，求出该树的节点个数。

完全二叉树的定义如下：

在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1 ~ 2h 个节点。

输入：root = [1,2,3,4,5,6]
输出：6
复制代码

基本思路

如果直接用递归求出节点个数也行，但是就没用到完全二叉树性质。

如果是满二叉树，类似这样,每一层都是满节点

      1                      
     /  \
    2    3    
   / \  / \
  4   5 6  7  h=3  count = 2^3 - 1
复制代码

假设一个满二叉树深度是 3 ，则节点数为 2 ^ 3 – 1 (2的三次方 – 1)

2^0 + 2^1 + 2^2 这就是这三层的节点数 1 + 2 + 4 = 7

我们推导满二叉树节点数为 2^h - 1 h 为二叉树深度

为什么？ count(h) = 2^0 (根/第一层) + 2^1(左右孩子/第二层) + 2^2(第三层节点数) + …
2^(h-1) = 1 + 2 + 4 + … 2^(h-1) 看出等比数列来吗, 等比求和,a1 = 1, q = 2, S = a1*(1-q^n) / (1-q) = 1*(1-2^h)/(1-2) = 2^h - 1

搞那么多其实就是为了得到一结论，如果是满二叉树，就没必要递归求了，直接公式求出数量。

写法实现

var countNodes = function(root) {
  if (root == null) {
    return 0;
  }
  // 判断是否是满二叉树，是的话直接公式求解
  let [leftHeight, rightHeight] = [0, 0]
  let [leftNode, rightNode] = [root, root]
  // 前提知道这是完全二叉树了，所以才可以用左右边高度相同判断是否满树
  while(leftNode) {
    leftHeight++
    leftNode = leftNode.left
  }
  while(rightNode) {
    rightHeight++
    rightNode = rightNode.right
  }
  if (leftHeight === rightHeight) {
    return 2 ** leftHeight - 1
  }
  return countNodes(root.left) + countNodes(root.right) + 1; // 加根 + 1
};
复制代码

94. 二叉树的最近公共祖先 (lowest-common-ancestor-of-a-binary-tree)

题目

leetcode 传送门

这里不贴题了，leetcode打开就行，题目大意：

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
复制代码

基本思想

要找p,q的公共祖先，分两种情况

当前节点是 root ，p 和 q 在不同子树中（左右一边一个）
当前节点是 root ，p 和 q 在相同子树中（都在左或者右）

从根节点遍历，递归向左右子树查询节点信息

如果左右子树查到节点都不为空，则表明 p 和 q 分别在左右子树中，因此，当前节点即为最近公共祖先
如果左右子树其中有一个不为空，则返回非空节点, 因为先被返回说明靠近根。

写法实现

var lowestCommonAncestor = function(root, p, q) {
  // 当 null 或者找到 p , q 就返回 (递归出口)
  if (!root || root == p || root == q) {
    return root
  }
  // 递归遍历左右子树
  let leftTree = lowestCommonAncestor(root.left, p, q)
  let rightTree = lowestCommonAncestor(root.right, p, q)
  // 分散在左右子树，直接返回根
  if (leftTree && rightTree) {
    return root
  }
  // 要不就返回先获得的，因为另一半树为空，先获得的必然是后面的父辈
  return leftTree ? leftTree : rightTree;
};
复制代码

另外向大家着重推荐下这位大哥的文章，非常深入浅出，对前端进阶的同学非常有作用，墙裂推荐！！！核心概念和算法拆解系列

今天就到这儿，想跟我一起刷题的小伙伴可以加我微信哦
搜索我的微信号infinity_9368，可以聊天说地
加我暗号 “天王盖地虎” 下一句的英文，验证消息请发给我
presious tower shock the rever monster，我看到就通过，暗号对不上不加哈，加了之后我会尽我所能帮你，但是注意提问方式，建议先看这篇文章：提问的智慧