Non-recursive solution in java


  • 0
    D
    public class Solution {
        public int countNodes(TreeNode root) {
            if (root == null) {
                return 0;
            }
            
            int leftHeight = height(root.left);
            int nodes = 0;
            
            while (root != null) {
                int rightHeight = height(root.right);
                
                if (leftHeight == rightHeight) {
                    nodes += (1 << leftHeight);
                    root = root.right;
                    leftHeight = rightHeight - 1;
                } else {
                    nodes += (1 << rightHeight);
                    root = root.left;
                    leftHeight = leftHeight - 1;
                }
            }
            
            return nodes;
        }
        
        private int height(TreeNode root) {
            int count = 0;
            
            while (root != null) {
                count++;
                root = root.left;
            }
            
            return count;
        }
    }
    

    The basic idea is to compare the tree height of left subtree (LST) and right subtree (RST). In my algorithm, the tree height is the number of nodes in the path from root to the left-most leave node. So if the height of LST is larger than the height of RST then the last leave node is in LST and RST is a full binary tree, vice versa.

    The number of nodes in a full binary tree is 2^h - 1. So (number of nodes in full LST/RST) + current root node = 2 ^ h - 1 + 1 = 2^h. Compute the remaining complete subtree.


  • 0
    T

    the result is not correct when test case is like [1,2,3,4], which is that the when leftHeight != rightHeight,
    the left subtree may also is not complete tree.


  • 0
    D

    thanks for pointing out, find a stupid bug in the answer. should be good now. In the 1,2,3,4 case though left subtress is not complete, the right subtree is complete, so we count all nodes in the right subtress and move to the left subtree.


Log in to reply
 

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