LeetCode-Count Complete Tree Nodes

我不是女神ヾ 2022-08-04 13:43 88阅读 0赞

Given a complete binary tree, count the number of nodes.

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 2hnodes inclusive at the last level h.

很显然，最笨方法就是遍历计数，dfs，bfs都是可以的，但是遍历的方法都是对Tree试用的，此题又要求complete binary tree的意义何在，可以自己提交一个遍历的方法，直接超时。

也就是这个要求要比O(n)还要低，所以自然就想起来binary search了，而二叉树本身就非常适合binary search。so 肯定用二分。

而到底怎么做呢？我们可以根据数的高度来跟左右子树比，这样就可以判处不完整的树到底在那一部分。看代码，非递归版的

public int countNodes(TreeNode root) {
    		int cnt = 0;
    		
    		int height = height(root);
    		while (root != null) {
    			if (height(root.right) == height-1) {
    				cnt += 1 << height-1;
    				root = root.right;
    			} else {
    				cnt += 1 << height-2;
    				root = root.left;
    			}
    			height--;
    		}
    		return cnt;
    	}
    	
    	private int height(TreeNode root) {
    		int cnt = 0;
    		while (root != null) {
    			cnt++;
    			root = root.left;
    		}
    		return cnt;
    	}

递归版的

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);
        }

细细品味二分，这样的二分。。。

[Wikipedia]: http://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees