LeetCode - Medium - 222. Count Complete Tree Nodes

柔情只为你懂 2022-10-07 06:50 43阅读 0赞

## Topic ##

*  Binary Search
 *  Tree

## Description ##

[https://leetcode.com/problems/count-complete-tree-nodes/][https_leetcode.com_problems_count-complete-tree-nodes]

Given the `root` of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between `1` and  2 h 2^h 2h nodes inclusive at the last level `h`.

Design an algorithm that runs in less than `O(n)` time complexity.

**Example 1:**

![079ef7a0e23613599404ff6e5801473e.png][]

Input: root = [1,2,3,4,5,6]
    Output: 6

**Example 2:**

Input: root = []
    Output: 0

**Example 3:**

Input: root = [1]
    Output: 1

**Constraints:**

*  The number of nodes in the tree is in the range  \[ 0 , 5 ∗ 1 0 4 \] \[0, 5 \* 10^4\] \[0,5∗104\].
 *   0 < = N o d e . v a l < = 5 ∗ 1 0 4 0 <= Node.val <= 5 \* 10^4 0<=Node.val<=5∗104
 *  The tree is guaranteed to be **complete**.

## Analysis ##

一个完整的完全树的个数： 1 + 2 + 4 + 8 + . . . + 2 h − 1 1 + 2 + 4 + 8 +... + 2^\{h-1\} 1\+2\+4\+8\+...\+2h−1

显然，加法式是以1为首项，公比为2，项个数为h 的等比数列的求和式。

代入求和公式得：

S h = a 1 ( 1 − q h ) 1 − q = 2 h − 1 S\_h= \\frac \{a\_1(1-q^h)\} \{1-q\}=2^h-1 Sh=1−qa1(1−qh)=2h−1

换成编程语言`S = 1 << h - 1`

解题**核心思想**：根据节点的左右子树的高度比较得出谁是更可能是完整的完全树，谁就能直接用求和公式得出子树的个数，然后在另一个子树递归刚才的过程求个数，最后将递归结果累加得出结果。

方法一：

> The height of a tree can be found by just going left. Let a single node tree have height 0. Find the height h of the whole tree. If the whole tree is empty, i.e., has height -1, there are 0 nodes.
> 
> Otherwise check whether the height of the right subtree is just one less than that of the whole tree, meaning left and right subtree have the same height.
> 
>  *  If yes, then the last node on the last tree row is in the right subtree and the left subtree is a full tree of height h-1. So we take the 2^h-1 nodes of the left subtree plus the 1 root node plus recursively the number of nodes in the right subtree.
>  *  If no, then the last node on the last tree row is in the left subtree and the right subtree is a full tree of height h-2. So we take the 2^(h-1)-1 nodes of the right subtree plus the 1 root node plus recursively the number of nodes in the left subtree.
> 
> Since I halve the tree in every recursive step, I have O(log(n)) steps. Finding a height costs O(log(n)). So overall O(log(n)^2).  
> [Link][]

方法二：个人对方法一作出稍微修改，增加可读性。

方法三：方法一的迭代版本。

方法四：看似暴力计算却暗含优化版。

> That would be O(n). But… the actual solution has a gigantic optimization. It first walks all the way left and right to determine the height and whether it’s a full tree, meaning the last row is full. If so, then the answer is just 2^height-1. And since always at least one of the two recursive calls is such a full tree, at least one of the two calls immediately stops. Again we have runtime O(log(n)^2).  
> [Link][]

方法五：更人钟爱的版本，因为他写法体现对称性。

## Submission ##

import com.lun.util.BinaryTree.TreeNode;
    
    public class CountCompleteTreeNodes { 
    	
    	//方法一：
        private int height(TreeNode root) { 
            return root == null ? -1 : 1 + height(root.left);
        }
        
        public int countNodes(TreeNode root) { 
            int h = height(root);
            return h < 0 ? 0 :
                   height(root.right) == h - 1 ? (1 << h) + countNodes(root.right)
                                             : (1 << h - 1) + countNodes(root.left);
        }
        
        //方法二：稍微修饰方法一
        private int height2(TreeNode root) { 
        	return root == null ? 0 : 1 + height2(root.left);
        }
        
        public int countNodes2(TreeNode root) { 
        	int h = height2(root);
        	return h == 0 ? 0 :
        		height2(root.right) == h - 1 ? // 
        				(1 << (h - 1)) + countNodes2(root.right) : // 
        				(1 << (h - 2)) + countNodes2(root.left);
        }
        
        //方法三：方法一的迭代版
        public int countNodes3(TreeNode root) { 
            int nodes = 0, h = height(root);
            while (root != null) { 
                if (height(root.right) == h - 1) { 
                    nodes += 1 << h;
                    root = root.right;
                } else { 
                    nodes += 1 << h - 1;
                    root = root.left;
                }
                h--;
            }
            return nodes;
        }
        
        //方法四：
        public int countNodes4(TreeNode root) { 
            if (root == null)
                return 0;
            TreeNode left = root, right = root;
            int height = 0;
            while (right != null) { 
                left = left.left;
                right = right.right;
                height++;
            }
            if (left == null)
                return (1 << height) - 1;
            return 1 + countNodes(root.left) + countNodes(root.right);
        }
        
        //方法五：方法一的对称写法形式
        public int countNodes5(TreeNode root) { 
            if (root == null)
                return 0;
            int lh = height2(root.left);
            int rh = height2(root.right);     
            if(lh == rh) 
               return (1 << lh) + countNodes5(root.right);  /*1(根节点) + (1<<lh)-1(完全左子树) + # of rightNode */               
            else 
               return (1 << rh) + countNodes5(root.left);  /*1(根节点) + (1<<rh)-1(完全右子树) + # of leftNode*/
        }
        
        
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    
    public class CountCompleteTreeNodesTest { 
    
    	@Test
    	public void test() { 
    		CountCompleteTreeNodes obj = new CountCompleteTreeNodes();
    
    		assertEquals(6, obj.countNodes(BinaryTree.integers2BinaryTree(1, 2, 3, 4, 5, 6)));
    		assertEquals(1, obj.countNodes(BinaryTree.integers2BinaryTree(1)));
    		assertEquals(0, obj.countNodes(null));
    	}
    	
    	@Test
    	public void test2() { 
    		CountCompleteTreeNodes obj = new CountCompleteTreeNodes();
    		
    		assertEquals(6, obj.countNodes2(BinaryTree.integers2BinaryTree(1, 2, 3, 4, 5, 6)));
    		assertEquals(1, obj.countNodes2(BinaryTree.integers2BinaryTree(1)));
    		assertEquals(0, obj.countNodes2(null));
    	}
    	
    	@Test
    	public void test3() { 
    		CountCompleteTreeNodes obj = new CountCompleteTreeNodes();
    		
    		assertEquals(6, obj.countNodes3(BinaryTree.integers2BinaryTree(1, 2, 3, 4, 5, 6)));
    		assertEquals(1, obj.countNodes3(BinaryTree.integers2BinaryTree(1)));
    		assertEquals(0, obj.countNodes3(null));
    	}
    	
    	@Test
    	public void test4() { 
    		CountCompleteTreeNodes obj = new CountCompleteTreeNodes();
    		
    		assertEquals(6, obj.countNodes4(BinaryTree.integers2BinaryTree(1, 2, 3, 4, 5, 6)));
    		assertEquals(1, obj.countNodes4(BinaryTree.integers2BinaryTree(1)));
    		assertEquals(0, obj.countNodes4(null));
    	}
    	
    	@Test
    	public void test5() { 
    		CountCompleteTreeNodes obj = new CountCompleteTreeNodes();
    		
    		assertEquals(6, obj.countNodes5(BinaryTree.integers2BinaryTree(1, 2, 3, 4, 5, 6)));
    		assertEquals(1, obj.countNodes5(BinaryTree.integers2BinaryTree(1)));
    		assertEquals(0, obj.countNodes5(null));
    	}
    }

[https_leetcode.com_problems_count-complete-tree-nodes]: https://leetcode.com/problems/count-complete-tree-nodes/
[079ef7a0e23613599404ff6e5801473e.png]: /images/20221005/a42f83e5e72c439c8409cf53f2078638.png
[Link]: https://leetcode.com/problems/count-complete-tree-nodes/discuss/61958/Concise-Java-solutions-O%28log%28n%292%29