L958. 二叉树的完全性检验 java

1. 从1开始当下标，最后节点下标==节点总数？true：false；

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int size=0,maxs=0;public boolean isCompleteTree(TreeNode root) {if(root==null) return  true;func(root,1);return size==maxs;}public void func(TreeNode node , int index){if(node==null) return ;size++;maxs=Math.max(maxs,index);   func(node.left,2*index);func(node.right,1+2*index);}
}

2. 标准BFS，层序遍历，出现空节点后再出现非空节点就不是，其他都是。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int size=0,maxs=0;public boolean isCompleteTree(TreeNode root) {if(root==null) return true;int cnt=0;Queue<TreeNode> q = new LinkedList<>();q.offer(root);while(!q.isEmpty()){TreeNode cur= q.poll();if(cur==null) cnt=1;else{if(cnt==1) return false;q.offer(cur.left);q.offer(cur.right);}}return  true;}
}