Traverse tree only once


  • 0
    D

    Idea is that when you are calculating depth, keep calculating the max diametere

    public class Result {
        public int depth;
        public int maxDiameter;
    }
    
    public class Solution {
        public int DiameterOfBinaryTree(TreeNode root) {
            Result res = CalcMaxD(root);
            return res.maxDiameter;
        }
        
        private Result CalcMaxD(TreeNode root) {
            if(root == null) {
                return new Result {
                    depth = 0,
                    maxDiameter = 0
                };
            }
            Result lR = CalcMaxD(root.left);
            Result rR = CalcMaxD(root.right);
            return new Result {
                depth = Math.Max(lR.depth,rR.depth) + 1,
                maxDiameter = Math.Max(lR.depth + rR.depth, Math.Max(lR.maxDiameter, rR.maxDiameter))
            } ;
        }
    }
    

Log in to reply
 

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