给定一个二叉树,确定他是否是一个完全二叉树。
完全二叉树的定义:若二叉树的深度为 h,除第 h 层外,其它各层的结点数都达到最大个数,第 h 层所有的叶子结点都连续集中在最左边,这就是完全二叉树。(第 h 层可能包含 [1~2h] 个节点)
数据范围:节点数满足
样例图1:
样例图2:
样例图3:
{1,2,3,4,5,6}
true
{1,2,3,4,5,6,7}
true
{1,2,3,4,5,#,6}
false
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return bool布尔型 */ bool isCompleteTree(TreeNode* root) { int maxLayer = 0; std::map<int,vector<TreeNode*>> table; std::function<void(TreeNode*,int)> dfs = [&](TreeNode* p, int layer) ->void { table[layer].push_back(p); maxLayer = max(maxLayer, layer); if(p->left){ dfs(p->left, layer + 1); } if(p->right){ dfs(p->right, layer + 1); } }; dfs(root,0); if(maxLayer == 0){ return true; } int num = table[maxLayer - 1].size(); if(num != pow(2,maxLayer-1)) { return false; } else{ bool flag = true; for(auto& node : table[maxLayer-1]){ if(!flag && (node->right||node->left)){ return false; } if(!node->right||!node->left) { flag = false; if(node->left == nullptr && node->right) { return false; } } } } return true; } };
package main import . "nc_tools" /* * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return bool布尔型 */ func isCompleteTree(root *TreeNode) bool { if root == nil { return true } notComplete := false queue := []*TreeNode{root} for len(queue) > 0 { tempQueue := []*TreeNode{} for _, node := range queue { if node == nil { notComplete = true continue } if notComplete { return false // 第二次出现空节点 } tempQueue = append(tempQueue, node.Left) tempQueue = append(tempQueue, node.Right) } queue = tempQueue } return true }
public boolean isCompleteTree (TreeNode root) { // write code here if(root == null) return true; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); TreeNode cur; boolean flag = false; while(!queue.isEmpty()){ cur = queue.poll(); if(cur == null){ flag = true; continue; } if(flag) return false; queue.offer(cur.left); queue.offer(cur.right); } return true; }
bool isCompleteTree(struct TreeNode* root ) { struct TreeNode **queue=(struct TreeNode*)malloc(sizeof(struct TreeNode*)*100); int f=-1,r=-1; queue[++r]=root; int flag=0; while(r!=f){ struct TreeNode *k=queue[++f]; if(k!=NULL){ if(flag) return 0; queue[++r]=k->left; queue[++r]=k->right; } else{ flag=1; } } return flag; }采用层次遍历 送给考研的大家 C版本
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return bool布尔型 */ public boolean isCompleteTree (TreeNode root) { // write code here Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); boolean flag = false; while(!queue.isEmpty()){ TreeNode node = queue.poll(); // 有右孩子没有左孩子 if(node.right != null && node.left == null) return false; // 遇到了左右孩子不双全的节点后,遇到了非叶子节点 if(flag && (node.left != null || node.right != null)) return false; // 遇到左右孩子不双全的节点 if((node.left != null && node.right == null) || (node.left == null && node.right == null)) flag = true; if(node.left != null) queue.offer(node.left); if(node.right != null) queue.offer(node.right); } return true; } }
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: bool isCompleteTree(TreeNode* root) { // 层序遍历 利用完全二叉树条件 if (root == nullptr) return true; queue<TreeNode* > que; que.push(root); while (!que.empty()) { TreeNode* cur = que.front(); que.pop(); if (cur != nullptr) { // 完全二叉树条件1:有右无左 返回false if (cur -> left == nullptr && cur -> right != nullptr) return false; // cur的左右子节点入队 que.push(cur -> left); que.push(cur -> right); } else // 遇到空节点 循环终止 break; } // 二次while判断不满足上述条件1(左无右有)后仍有不满足: // 条件2 完全二叉树叶子节点须从左至右依次排列 // 队列还为空 如果头结点非空 则返回false 空则出队 while (!que.empty()) { if (que.front() != nullptr) return false; else que.pop(); } return true; } };
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return bool布尔型 */ public boolean isCompleteTree (TreeNode root) { // write code here //层序遍历,在队列里加null。完全二叉树当poll出null时,后面应该都是null //非完全二叉树,poll出一个null后,后面还有非null元素 //层序遍历,需要加null进去判断(通常不用加null) if(root == null) return true; LinkedList<TreeNode> queue = new LinkedList<>(); queue.offer(root); boolean isLast = false; while(!queue.isEmpty()){ TreeNode t = queue.poll(); //如果是完全二叉树,t应该一直为null,直到结束 if(t == null){ isLast = true; continue; } //非完全二叉树,出现null后又出现非null元素 if(isLast){ return false; } //加入的是t的左节点和右节点 queue.offer(t.left); queue.offer(t.right); } return true; } }
public boolean isCompleteTree (TreeNode root) { // write code here Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); if (node != null) { if (node.right != null && node.left == null) return false; queue.offer(node.left); queue.offer(node.right); } else { break; } } while (!queue.isEmpty()) { if (queue.poll() != null) { return false; } } return true; }
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return bool布尔型 */ bool isCompleteTree(TreeNode* root) { // write code here if(!root)return 1; queue<TreeNode*> q; q.push(root); while(!q.empty()) {//空指针也可以压入 int sz = q.size(); while(sz--) { auto cur = q.front(); if(!cur){//域间空指针后看后没是不是全是空指针 while(!q.empty() && !q.front()) q.pop(); if(q.empty())return 1;//全是空 else return 0;//不全是空 } q.pop(); // 空指针也压进去 q.push(cur->left); q.push(cur->right); } } return 1; } };
public class Solution { int ans = 0; int helper(TreeNode root, int idx){ if(root == null) return 0; ans = Math.max(ans, idx); return 1 + helper(root.left, idx * 2) + helper(root.right, idx * 2 + 1); } public boolean isCompleteTree (TreeNode root) { return helper(root, 1) == ans; } }
public boolean isCompleteTree (TreeNode root) { // write code here if(root == null) return true; Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); boolean isHasLeft = true; while(!queue.isEmpty()) { TreeNode poll = queue.poll(); if(poll == null) isHasLeft = false; else{ if(isHasLeft == false) return isHasLeft; queue.add(poll.left); queue.add(poll.right); } } return true; }
# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param root TreeNode类 # @return bool布尔型 # class Solution: def isCompleteTree(self , root: TreeNode) -> bool: # write code here if root is None: return True queue = [root] is_missing_child = False while len(queue) > 0: node = queue.pop(0) # 针对缺失节点的情况进行判断 if node is None: is_missing_child = True continue elif is_missing_child: return False # 将左右子节点加入队列 queue.append(node.left) queue.append(node.right) return True
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ #include <queue> #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return bool布尔型 */ bool isCompleteTree(TreeNode* root) { if (root == nullptr) return true; queue<TreeNode*> s; vector<int> v; int size = 0; s.push(root); while (!s.empty()) { TreeNode* now = s.front(); s.pop(); if(now!=nullptr){ v.push_back(now->val); s.push(now->left); s.push(now->right); } else{ v.push_back(-1); } size++; } bool flag =true; for(int i=size-1;i>0;i--){ if(v[i]!=-1){ flag=false; } if(v[i]==-1&&!flag) return false; } return true; } };
func isCompleteTree(root *TreeNode) bool { var queue = list.New() var count = 0 queue.PushBack(root) for queue.Len() != 0 { size := queue.Len() count++ mayCount := int(math.Pow(float64(2), float64(count-1))) var isComplete = true for i := 0; i < size; i++ { node := queue.Front().Value.(*TreeNode) queue.Remove(queue.Front()) if size != mayCount && (node.Left != nil || node.Right != nil) { return false } if node.Right != nil && node.Left == nil { return false } if (node.Left != nil || node.Right != nil) && isComplete == false { return false } if node.Left == nil || node.Right == nil { isComplete = false } if node.Left != nil { queue.PushBack(node.Left) } if node.Right != nil { queue.PushBack(node.Right) } } } return true // write code here }
public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return bool布尔型 */ public boolean isCompleteTree (TreeNode root) { // 如果根为null,就返回true if(root == null){ return true; } /* * 判断不是完全二叉树,有3种情况: * 1. 左子节点为空,右子节点不为空 * 2. 当左子节点不为空,右子节点为空的时候,后面继续迭代当前层时,只要发现还有节点 它就不是完全二叉树 * 2. 当左子节点不为空,右子节点为空的时候,后面继续迭代下一层时,只要发现还有下一层有节点,它就不是完全二叉树 */ // 定义一个链表,用于保存每一层的节点 LinkedList<TreeNode> linked = new LinkedList<>(); linked.add(root); // 先添加根节点 boolean flag = false; // 定义一个状态码,当出现右子节点为null时,就设置为true int size; // 保存循环中每一次链表的长度 TreeNode treeNode; // 保存每一次取出的链表头节点 // 链表不为空 循环继续 while (!linked.isEmpty()){ // 获取链表长度 size = linked.size(); // 根据size 进行循环 依次取出链表头节点 for (int i = 0; i < size; i++) { // 取出头节点 treeNode = linked.removeFirst(); // 只要左子节点为空,右子节点不为空 直接返回false if(treeNode.left == null && treeNode.right != null) return false; // 能执行到这里,只有以下两种情况 // 1.treeNode.left!=null (right可能 null || !null) // 2.treeNode.left ==null treeNode.right==null // 只要左子节点有值 就添加链表 if(treeNode.left !=null){ // 如果flag为真,表示在这之前的层级或者当前层级中 已经出现了right为空的情况, // 既然已经出现过right为空的情况 那么此if代码块还能进入,已经不是完全二叉树了。就返回false // 首次执行到这,flag一定为false if(flag) return false; // 链表添加节点 linked.add(treeNode.left); } // right!=null 链表添加节点 if(treeNode.right != null)linked.add(treeNode.right); // right为空,flag设置为true else flag = true; } } // 循环结束,表示该树符合完全二叉树,返回true return true; } }
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return bool布尔型 */ bool isCompleteTree(TreeNode* root) { // 时间复杂度O(N),空间复杂度O(N) if (root == nullptr) return true; queue<TreeNode*> que; que.push(root); bool flag = false; while (!que.empty()) { TreeNode* node = que.front(); que.pop(); if (node->left) { if (flag) return false; que.push(node->left); } else flag = true; if (node->right) { if (flag) return false; que.push(node->right); } else flag = true; } return true; } };