Java recursion and divide & conquor


  • 0
    B

    Divide the problem into 2:

    1. the longest path goes through root. This becomes new problem of calculating longest path from root going left plus longest path from root going right.

    2. The longest path does not include root. This becomes sub problem of sub tree left and right

    finally get the max of the 3 results.

    I don't think this is EASY problem. unless I over complicated the problem.

    public int diameterOfBinaryTree(TreeNode root) {
        
        if (root == null) 
            return 0;
        
        int both = 0;
        
        if (root.left != null)
            both += longestPath(root.left) + 1;
        if (root.right != null)
            both += longestPath(root.right) + 1;
        
        int left = diameterOfBinaryTree(root.left);
        
        int right = diameterOfBinaryTree(root.right);
        
        int ret = Math.max(Math.max(left, right), both);
        
        return ret;
        
        
    }
    
    private int longestPath(TreeNode root){
        
        if (root == null || (root.left == null && root.right == null))
            return 0;
        return (1 + Math.max(longestPath(root.left), longestPath(root.right)));
    
    }

  • 0
    L

    Yeah looks like you have overly complicated the problem by adding extra code. I am doing the same as you but you don't need to check for root.left or root.right==null since your exit condition of root==null should not cause any NPE. Here is my code:

    public class Solution {
        public int diameterOfBinaryTree(TreeNode root) {
            if(root==null) {
                return 0;
            }
            int leftDiameter = diameterOfBinaryTree(root.left);
            int rightDiameter = diameterOfBinaryTree(root.right);
            int rootHeight = maxdepth(root.left) + maxdepth(root.right);
            
            return Math.max(leftDiameter,Math.max(rightDiameter,rootHeight));
        }
        
        private int maxdepth(TreeNode root) {
            if(root==null) {
                return 0;
            }        
            return 1+ Math.max(maxdepth(root.left),maxdepth(root.right));
        }
    }
    

Log in to reply
 

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