JAVA DFS solution super easy to understand :)


  • 0
    H

    public class Solution {

    private int diameter = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        
        //Algo thinking: recursive DFS: maxDiamter go through a node = left.maxDepth + right.maxDepth + 1
        
        // time = O(N), space = O(1)
        
        if (root == null) return 0;
        
        dfs(root);
        
        return diameter - 1;
    }
    
    private int dfs(TreeNode root) {
        
        if (root == null) return 0;
        
        int leftDepth = dfs(root.left);
        int rightDepth = dfs(root.right);
        
        diameter = Math.max(diameter, leftDepth + rightDepth + 1);
        
        return Math.max(leftDepth, rightDepth) + 1;
    }
    

    }


Log in to reply
 

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