You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

958. 二叉树的完全性检验 - Check Completeness of a Binary Tree

. 2 min read

【层级遍历 - 迭代】 【层级遍历 - 递归】

给定一个二叉树,确定它是否是一个完全二叉树。

百度百科中对完全二叉树的定义如下:

若设二叉树的深度为 h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。(注:第 h 层可能包含 1~ 2h 个节点。)

Example:

示例 1:

img
输入:[1,2,3,4,5,6]
输出:true
解释:最后一层前的每一层都是满的(即,结点值为 {1} 和 {2,3} 的两层),且最后一层中的所有结点({4,5,6})都尽可能地向左。

示例 2:

img
输入:[1,2,3,4,5,null,7]
输出:false
解释:值为 7 的结点没有尽可能靠向左侧。

Solutions

  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }

Solution 【层级遍历 - 迭代】 ( 6ms)

class Solution {
  public boolean isCompleteTree(TreeNode root) {
    if (root == null) {
      return false;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    TreeNode curNode;
    queue.offer(root);
    while (true) {
      curNode = queue.poll();
      if(curNode == null) {
        break;
      }
      queue.offer(curNode.left);
      queue.offer(curNode.right);
    }

    while (!queue.isEmpty()) {
      if (queue.poll() != null) {
        return false;
      }
    }
    return true;
  }
}

Solution 【层级遍历 - 递归】 ( 5ms)

class Solution {
    public boolean isCompleteTree(TreeNode root) {
        return helper(root)[0] >= 0;
    }
    
    public int[] helper(TreeNode node) {
        if (node == null) return new int[]{1, 0};
        
        int[] leftRes = helper(node.left);
        if (leftRes[0] < 0) return leftRes;
        
        int[] rightRes = helper(node.right);
        if (rightRes[0] < 0) return rightRes;
        
        if (leftRes[1] == rightRes[1] && leftRes[0] == 1) {
            return new int[]{rightRes[0], leftRes[1] + 1};
        }
        else if (leftRes[1] == rightRes[1] + 1 && rightRes[0] == 1) {
            return new int[]{0, leftRes[1] + 1};
        }
        else return new int[]{-1, 0};
    }
}

Notes

while中的小优化,提高运行速度。