Easy java solution (but a bit long)


  • 2
    T
    /**
     * 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 countNodes(TreeNode root) {
            int hl = leftHeight(root);
            int hr = rightHeight(root);
            if (hl == hr) {
                return pow(hl) - 1;
            } else {
                // must be that hl = hr +1
                
                // if the left child tree is "full"
                if (rightHeight(root.left) +1 == hl)
                return pow(hl-1)-1 + 1 + countNodes(root.right);
                else
                return countNodes(root.left) + 1 + pow(hr-1)-1 ;
            }
            
    
        }
        
        // 2 to the power of n
        int pow(int n) {
            int result = 1;
            while(n>0) {
                result *=2; n--;
            }
            return result;
        }
        
        int leftHeight(TreeNode root) {
            int l = 0;
            while(root !=null) {
                l++;
                root = root.left;
            }
            return l;
        }
        int rightHeight(TreeNode root) {
            int l = 0;
            while(root !=null) {
                l++;
                root = root.right;
            }
            return l;
        }   
        
    }

  • 0
    N

    it may not have the best performance ,but do have the most clear thoughts ,thank u !


  • 0

    interesting is that if use Math.pow(), will get TLE. Use public int
    pow(int n) {
    return 1<<n;
    }
    will improve time complexity a lot


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.