Alibi

My Life is Getting Better

Leetcode[222] Count Complete Tree Nodes

21 Nov 2015

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

###Python

# 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 countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        if not root.left and not root.right:
            return 1
        if not root.left or not root.right:
            return 2
        left = self.leftDepth(root.left)
        right = self.rightDepth(root.right)
        if left == right:
            return (1 << (left + 1)) - 1
        else:
            return self.countNodes(root.left) + self.countNodes(root.right) + 1
        
    def leftDepth(self, root):
        if not root:
            return 0
        count = 1
        while root.left:
            root = root.left
            count += 1
        return count
    def rightDepth(self, root):
        if not root:
            return 0
        count = 1
        while root.right:
            root = root.right
            count += 1
        return count

###Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    
    public int rightNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int count = 1;
        while (root.right != null) {
            root = root.right;
            count++;
        }
        return count;
    }
    
    public int leftNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int count = 1;
        while (root.left != null) {
            root = root.left;
            count++;
        }
        
        return count;
    }
    
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int leftH = leftNodes(root);
        int rightH = rightNodes(root);
        if (leftH == rightH) {
            return (int)Math.pow(2, leftH - 1) - 1;
        }
        
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

###Points

参考LeetCode Discuss：https://leetcode.com/discuss/38899/easy-short-c-recursive-solution 如果当前子树的“极左节点”（从根节点出发一路向左）与“极右节点”（从根节点出发一路向右）的高度h相同，则当前子树为满二叉树，返回2^h - 1 否则，递归计算左子树与右子树的节点个数。

该方法的时间复杂度为O(h^2)，因为最耗时的操作是计算以某个节点为根节点的树的高度，最差情况下扫描次数为（1+2+…+h）*2。

Related Posts