Recursive Java Solution, corrects bug in other solution & includes test cases


  • 0
    Y

    Make sure to reset the global variable in case the method diameterOfBinaryTree gets called more than once. Otherwise, previous calls to that method could produce an incorrect result. I have spotted this bug in other people's proposed solutions.

    public class Java_0543_Diameter_of_Binary_Tree {
        private int longestDistanceWholeTree = 0;
        public int diameterOfBinaryTree(TreeNode root) {
            longestDistanceWholeTree = 0;  // Important to reset the global variable in case this method gets called more than once. 
            longestBranch(root);
            return longestDistanceWholeTree;
        }
        public int longestBranch(TreeNode root) {
            int longestDistance = 0;
            if (root == null) {
            	longestDistance = -1;
            } else {
            	int longestDistanceLeft = longestBranch(root.left) + 1;
            	int longestDistanceRight= longestBranch(root.right) + 1;
            	longestDistanceWholeTree = Math.max(longestDistanceWholeTree, longestDistanceLeft + longestDistanceRight);
            	longestDistance = Math.max(longestDistanceLeft, longestDistanceRight);
            }
            return longestDistance;
        }
        
    	public static void main(String[] args) {
    		Java_0543_Diameter_of_Binary_Tree solution = new Java_0543_Diameter_of_Binary_Tree();
    		TreeNode t;
    		t = new TreeNode(1);
    		t.right = new TreeNode(3);
    		t.left = new TreeNode(2);
    		t.left.left = new TreeNode(4);
    		t.left.right = new TreeNode(5);
    		
    		assert(solution.diameterOfBinaryTree(t) == 3);
    
    		t = new TreeNode(1);
    		t.right = new TreeNode(3);
    		t.left = new TreeNode(2);
    		t.left.left = new TreeNode(4);
    		t.left.right = new TreeNode(5);
    		t.left.left.left = new TreeNode(44);
    		t.left.left.left.left = new TreeNode(444);
    		t.left.right.right = new TreeNode(55);
    		t.left.right.right.right = new TreeNode(555);
    		
    		assert(solution.diameterOfBinaryTree(t) == 6);
    
    		t = new TreeNode(1);
    		assert(solution.diameterOfBinaryTree(t) == 0);
    
    		t = new TreeNode(1);
    		t.right = new TreeNode(3);
    		
    		assert(solution.diameterOfBinaryTree(t) == 1);
    
        	System.out.println(solution.getClass() + ": All test cases passed!!! Great job!!! :D");
    	}
    
    }
    

Log in to reply
 

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