Swift O(n) solution - PostOrder Traversal without global variable


  • 0
    class Solution {
        func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
            guard let root = root else {
                return 0
            }
            
            var longestPath = 0
            
            maxDepth(root, &longestPath)
            
            return longestPath
        }
        
        func maxDepth(_ root: TreeNode?, _ longestPath: inout Int) -> Int {
            guard let root = root else {
                return 0
            }
            
            let leftMaxDepth = maxDepth(root.left, &longestPath)
            let rightMaxDepth = maxDepth(root.right, &longestPath)
            
            longestPath = max(longestPath, leftMaxDepth + rightMaxDepth)
            
            return max(leftMaxDepth, rightMaxDepth) + 1
        }
    }
    

Log in to reply
 

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