Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/222.html

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

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

 

Example 1:

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 * 104].
  • 0 <= Node.val <= 5 * 104
  • The tree is guaranteed to be complete.

Algorithm

First, we need a getHeight function, which is used to count the maximum height of the left subtree of the current node.

  • Call the getHeight function on the current node to get the maximum height h of the left subtree. If returned is -1, it means that the current node does not exist and returns 0 directly.
  • Otherwise, call the getHeight function on the right child.
    • If the return value is h-1, it means that the left sub-tree is a perfect binary tree, and the number of nodes in the left sub-tree is 2^h-1. Adding the current node, there are 2^h in total, that is, 1<<h,
      • then, add the return value of calling the recursive function on the right child node.
    • If the return value of calling the getHeight function on the right subnode is not h-1, it means that the right subtree must be a perfect tree, and the height is h-1,
      • then the number of summary points is 2^(h-1) -1, plus the current node is 2^(h-1), that is, 1<<(h-1), and then add the return value of calling the recursive function on the left child node

Code

  • 
    public class Count_Complete_Tree_Nodes {
        /**
         * Definition for a binary tree node.
         * public class TreeNode {
         *     int val;
         *     TreeNode left;
         *     TreeNode right;
         *     TreeNode(int x) { val = x; }
         * }
         */
    
        public class Solution_optimize {
    
            public int countNodes(TreeNode root) {
    
                int res = 0;
                int h = getHeight(root); // here h is actually h-1
    
                if (h < 0) return 0;
    
                if (getHeight(root.right) == h - 1) {
                    return (1 << h) + countNodes(root.right);
                } else { // getHeight(root.right) == h - 2
                    return (1 << (h - 1)) + countNodes(root.left);
                }
            }
    
            int getHeight(TreeNode node) {
                return node != null ? (1 + getHeight(node.left)) : -1;
            }
        }
    
        public class Solution {
            public int countNodes(TreeNode root) {
                if (root == null) {
                    return 0;
                }
    
                int leftHeight = findLeftHeight(root);
                int rightHeight = findRightHeight(root);
    
                if (leftHeight == rightHeight) {
                    return (2 << (leftHeight - 1)) - 1;
                }
    
                return 1 + countNodes(root.left) + countNodes(root.right);
            }
    
            private int findLeftHeight(TreeNode root) {
                if (root == null) {
                    return 0;
                }
    
                int height = 1;
    
                while (root.left != null) {
                    height++;
                    root = root.left;
                }
    
                return height;
            }
    
            private int findRightHeight(TreeNode root) {
                if (root == null) {
                    return 0;
                }
    
                int height = 1;
    
                while (root.right != null) {
                    height++;
                    root = root.right;
                }
    
                return height;
            }
        }
    }
    
    ############
    
    /**
     * 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 int countNodes(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int left = depth(root.left);
            int right = depth(root.right);
            if (left == right) {
                return (1 << left) + countNodes(root.right);
            }
            return (1 << right) + countNodes(root.left);
        }
    
        private int depth(TreeNode root) {
            int d = 0;
            for (; root != null; root = root.left) {
                ++d;
            }
            return d;
        }
    }
    
  • // OJ: https://leetcode.com/problems/count-complete-tree-nodes/
    // Time: O(H^2)
    // Space: O(H)
    class Solution {
        int countLeft(TreeNode *root) {
            int cnt = 0;
            for (; root; ++cnt, root = root->left);
            return cnt;
        }
        int countRight(TreeNode *root) {
            int cnt = 0;
            for (; root; ++cnt, root = root->right);
            return cnt;
        }
    public:
        int countNodes(TreeNode* root) {
            if (!root) return 0;
            int left = countLeft(root), right = countRight(root);
            if (left == right) return (1 << left) - 1;
            return countNodes(root->left) + countNodes(root->right) + 1;
        }
    };
    
  • # 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 countNodes(self, root: Optional[TreeNode]) -> int:
            def depth(root):
                d = 0
                while root:
                    d += 1
                    root = root.left
                return d
    
            if root is None:
                return 0
            left, right = depth(root.left), depth(root.right)
            if left == right:
                # left child subtree: (1<<left)-1
                # plus root: +1
                # so total except right subtree: (1<<left)
                return (1 << left) + self.countNodes(root.right)
            else: # left = right+1
                return (1 << right) + self.countNodes(root.left)
    
    ############
    
    '''
    >>> 2 ** 3
    8
    >>> 3 ** 2
    9
    '''
    
    
    # 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 getHeight(self, root):
        height = 0
        while root:
          height += 1
          root = root.left
        return height
    
      def countNodes(self, root):
        count = 0
        while root:
          l, r = map(self.getHeight, (root.left, root.right))
          if l == r:
            count += 2 ** l
            root = root.right
          else:
            count += 2 ** r
            root = root.left
        return count
    
    
  • /**
     * Definition for a binary tree node.
     * type TreeNode struct {
     *     Val int
     *     Left *TreeNode
     *     Right *TreeNode
     * }
     */
    func countNodes(root *TreeNode) int {
    	if root == nil {
    		return 0
    	}
    	left, right := depth(root.Left), depth(root.Right)
    	if left == right {
    		return (1 << left) + countNodes(root.Right)
    	}
    	return (1 << right) + countNodes(root.Left)
    }
    
    func depth(root *TreeNode) (d int) {
    	for ; root != nil; root = root.Left {
    		d++
    	}
    	return
    }
    
  • /**
     * Definition for a binary tree node.
     * function TreeNode(val, left, right) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.left = (left===undefined ? null : left)
     *     this.right = (right===undefined ? null : right)
     * }
     */
    /**
     * @param {TreeNode} root
     * @return {number}
     */
    var countNodes = function (root) {
        const depth = root => {
            let d = 0;
            for (; root; root = root.left) {
                ++d;
            }
            return d;
        };
        if (!root) {
            return 0;
        }
        const left = depth(root.left);
        const right = depth(root.right);
        if (left == right) {
            return (1 << left) + countNodes(root.right);
        }
        return (1 << right) + countNodes(root.left);
    };
    
    
  • /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     public int val;
     *     public TreeNode left;
     *     public TreeNode right;
     *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    public class Solution {
        public int CountNodes(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int left = depth(root.left);
            int right = depth(root.right);
            if (left == right) {
                return (1 << left) + CountNodes(root.right);
            }
            return (1 << right) + CountNodes(root.left);
        }
    
        private int depth(TreeNode root) {
            int d = 0;
            for (; root != null; root = root.left) {
                ++d;
            }
            return d;
        }
    }
    
  • use std::cell::RefCell;
    use std::rc::Rc;
    
    impl Solution {
        pub fn count_nodes(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
            if let Some(node) = root {
                let node = node.borrow();
                let left = Self::depth(&node.left);
                let right = Self::depth(&node.right);
                if left == right {
                    Self::count_nodes(node.right.clone()) + (1 << left)
                } else {
                    Self::count_nodes(node.left.clone()) + (1 << right)
                }
            } else {
                0
            }
        }
    
        fn depth(root: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
            if let Some(node) = root {
                Self::depth(&node.borrow().left) + 1
            } else {
                0
            }
        }
    }
    
    

All Problems

All Solutions