Check if a Binary Tree is Complete Binary Tree
A Complete Binary Tree is a Binary Tree where each level is completely filled. For example, all the trees below are complete Binary trees
https://reeestart.wordpress.com/2016/06/24/google-is-complete-tree/
Read full article from Check if a Binary Tree is Complete Binary Tree
A Complete Binary Tree is a Binary Tree where each level is completely filled. For example, all the trees below are complete Binary trees
Height=1 Height=2 Height=3
-------- -------- --------
A A A
/ \ / \
B C B C
/ \ / \
D E F G
And the trees below are not Complete (because there are holes in between):
A A A
/ / \ / \
B B C B C
\ / \ /
D D E F
Correct Solution-1: Combine above two wrong solutions
If we combine the other two solutions. i.e All the leaf nodes should be at the same level AND all the nodes should have either zero or two childs.
Correct Solution-2: Use equation between height and number of nodes
int getHeight(Node* root) { if (root == NULL) return 0; // Compute height of each tree int heightLeft = getHeight(root->lptr); int heightRight = getHeight(root->rptr); /* use the larger one */ if (heightLeft > heightRight) return(heightLeft + 1); else return(heightRight + 1);}/** * Count the total number of nodes in a Binary tree. */int countNodes(Node* r){ if(r == NULL) return 0; return 1 + countNodes(r->rptr) + countNodes(r->lptr); } |
The two functions above can be merged into one, so that the tree is traversed only once. Pass a countparameter as a reference parameter to the getHeight function and increment it once in each recursive function call. The time complexity will still be O(n) but we will gain in the constant factor (In this case the tree is traversed twice – once to compute the height and then to count the number of nodes).
// Helper function. to compute x^n. Assumes n to be positive.int exponent(int x, int n){ int pow = 1; int i=0; for(i=0; i<n; i++) pow *= x; return pow;}/** * returns true if a binary tree is complete binary tree, false otherwise */int checkCompleteTree(Node* r){ if(r == NULL) return true; int h = getHeight(r); int n = countNodes(r); if(n == exponent(2,h)-1) return 1; else return 0;}
给一棵binary tree，判断它是不是complete tree.
[Analysis]
有必要整理一下各种binary tree的区别。
有必要整理一下各种binary tree的区别。
Complete tree: 除了leaves，所有层都满，最后一层as left as possible
Full tree: 每个node要么没有child，要么就有两个，任何层都不一定是满的
Perfect tree: Complete tree + Full tree
[Solution]
Level Order traversal
一旦发现某个node没有children或者只有left child，那么从此以后的所有node都不能有任何children.
Level Order traversal
一旦发现某个node没有children或者只有left child，那么从此以后的所有node都不能有任何children.
不同于检查full tree可以用递归来实现，就算两个subtree都是complete的，也不能说明root就是complete的。
如果Follow up问如果计算complete tree有多少个node, 请参考Leetcode222 Count Complete Tree Nodes 这题可以用递归实现O(logn)的算法。
public boolean isCompleteTree(TreeNode root) { if (root == null) { return false; } Queue<TreeNode> q = new LinkedList<>(); q.offer(root); boolean canHaveChild = true; while (!q.isEmpty()) { int size = q.size(); for (int i = 0; i < size; i++) { TreeNode curr = q.poll(); if (curr.left != null && curr.right != null) { if (!canHaveChild) return false; q.offer(curr.left); q.offer(curr.right); } else if (curr.left == null && curr.right != null) { return false; } else if (curr.left != null && curr.right == null) { if (!canHaveChild) return false; canHaveChild = false; q.offer(curr.left); } else if (curr.left == null && curr.right == null) { canHaveChild = false; } } } return true; }