Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/958.html
958. Check Completeness of a Binary Tree (Medium)
Given a binary tree, determine if it is a complete binary tree.
Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
Example 1:
Input: [1,2,3,4,5,6] Output: true Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.
Example 2:
Input: [1,2,3,4,5,null,7] Output: false Explanation: The node with value 7 isn't as far left as possible.
Note:
- The tree will have between 1 and 100 nodes.
Companies:
Facebook
Related Topics:
Tree
Solution 1.
Use level order traversal. After visiting a node that has at least one null
child, all the subsequent nodes must be leaf nodes.
// OJ: https://leetcode.com/problems/check-completeness-of-a-binary-tree/
// Time: O(N)
// Space: O(N)
class Solution {
public:
bool isCompleteTree(TreeNode* root) {
if (!root) return true;
queue<TreeNode*> q;
q.push(root);
bool onlyLeafNow = false;
while (q.size()) {
int cnt = q.size();
while (cnt--) {
root = q.front();
q.pop();
if (!root->left && root->right) return false;
if (onlyLeafNow && (root->left || root->right)) return false;
if (root->left) q.push(root->left);
if (root->right) q.push(root->right);
if (!root->left || !root->right) onlyLeafNow = true;
}
}
return true;
}
};
-
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isCompleteTree(TreeNode root) { if (root == null) return true; Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); int levelNodes = 1; while (!queue.isEmpty()) { int size = queue.size(); if (size == levelNodes) { boolean flag = true; for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); TreeNode left = node.left, right = node.right; if (left == null && right != null) return false; if (left != null) queue.offer(left); if (right != null) queue.offer(right); if (!flag && (left != null || right != null)) return false; if (flag && (left == null || right == null)) flag = false; } } else { for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); if (node.left != null || node.right != null) return false; } } levelNodes <<= 1; } return true; } } ############ /** * 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 { public boolean isCompleteTree(TreeNode root) { Deque<TreeNode> q = new LinkedList<>(); q.offer(root); while (q.peek() != null) { TreeNode node = q.poll(); q.offer(node.left); q.offer(node.right); } while (!q.isEmpty() && q.peek() == null) { q.poll(); } return q.isEmpty(); } }
-
// OJ: https://leetcode.com/problems/check-completeness-of-a-binary-tree/ // Time: O(N) // Space: O(N) class Solution { public: bool isCompleteTree(TreeNode* root) { if (!root) return true; queue<TreeNode*> q; q.push(root); bool onlyLeafNow = false; while (q.size()) { int cnt = q.size(); while (cnt--) { root = q.front(); q.pop(); if (!root->left && root->right) return false; if (onlyLeafNow && (root->left || root->right)) return false; if (root->left) q.push(root->left); if (root->right) q.push(root->right); if (!root->left || !root->right) onlyLeafNow = true; } } return true; } };
-
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isCompleteTree(self, root: TreeNode) -> bool: q = deque([root]) while q: node = q.popleft() if node is None: break q.append(node.left) q.append(node.right) return all(node is None for node in q) ############ # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def isCompleteTree(self, root): """ :type root: TreeNode :rtype: bool """ if not root: return True res = [] que = collections.deque() que.append(root) hasNone = False while que: size = len(que) for i in range(size): node = que.popleft() if not node: hasNone = True continue if hasNone: return False que.append(node.left) que.append(node.right) return True
-
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func isCompleteTree(root *TreeNode) bool { q := []*TreeNode{root} for q[0] != nil { root = q[0] q = q[1:] q = append(q, root.Left) q = append(q, root.Right) } for len(q) > 0 && q[0] == nil { q = q[1:] } return len(q) == 0 }