题解 | #判断一棵二叉树是否为搜索二叉树和完全二叉树#

那么多人，抄答案抄的错的。
判断二叉完全树，为什么排名前面这个算法是错的呢？

// 错误算法
var complete = function(root){
    if(!root)return true;
    if(!root.left && root.right){
        return false
    }
    return complete(root.left) && complete(root.right);
}

因为这个算法只是排除了“左子不存在&&右子存在”这个场景
还有两个关键场景没排除：
1.节点不满的层级 > 1
2.堂弟存在堂兄不存在
晒出我的算法，没有用递归

/**
 * 判断二叉树是不是完全二叉树
 * @param {TreeNode} root
 * @returns
 */
function judgeBCT(root) {
  if (!root) return false;

  const allLevels = [];
  let buffer = [root];

  while (buffer.length) {
    allLevels.push(buffer);
    let currLv = buffer; // 当前考察的层
    buffer = []; // 遍历当前层，把子代存入buffer

    // 判断当前层是否满
    const currLvIdx = allLevels.length - 1;
    const currLvFull = currLv.length === Math.pow(2, currLvIdx);

    for (let i = currLv.length - 1; i >= 0; i--) {
      const node = currLv[i];

      let childNum = 0;
      if (node.right) {
        if (!currLvFull || !node.left) {
          return false; // 有右子，当前层不满或者无左子，一定是非完全二叉树
        }

        childNum++;
        buffer.unshift(node.right);
      }

      if (node.left) {
        if (!currLvFull) {
          return false; // 当前层不满却有左子，一定是非完全二叉树
        }
        childNum++;
        buffer.unshift(node.left);
      }

      // 当前节点后代不满，本层弟弟节点却有后代, 肯定不是完全二叉树
      if (childNum < 2 && buffer.length > childNum) {
        return false;
      }
    }
  }

  return true;
}