Given a binary tree, print the maximum path sum from one leaf node to another leaf node.

Question

Dmitry · Accepted Answer

class TreeNode {
    var data: Int
    var left: TreeNode?
    var right: TreeNode?
    
    init(data: Int) {
        self.data = data
    }
}

class Tree {
    var root: TreeNode?
    
    func add(data: Int) {
        let newNode = TreeNode(data: data)
        guard root != nil else {
            root = newNode
            return
        }
        var node = root!
        while true {
            if data * node.data {
                if node.left == nil {
                    node.left = newNode
                    break
                } else {
                    node = node.left!
                }
            } else {
                if node.right == nil {
                    node.right = newNode
                    break
                } else {
                    node = node.right!
                }
            }
        }
    }
}

class Problem {
    var tree = Tree()
    var bestSum: Int?
    
    func getMaxSumToLeaves(node: TreeNode?, sum: Int) -> Int {
        guard let node = node else {
            return sum
        }
        let sumFromRoot = sum + node.data
        let maxSumLeft = getMaxSumToLeaves(node: node.left, sum: sum + node.data)
        let maxSumRight = getMaxSumToLeaves(node: node.right, sum: sum + node.data)
        let maxSumToLeaves = max(maxSumLeft, maxSumRight)
        let sum = maxSumLeft + maxSumRight - sumFromRoot * 2 + node.data
        if bestSum == nil || sum > bestSum! {
            bestSum = sum
        }
        return maxSumToLeaves
    }
    
    func solve() {
        guard let root = tree.root else {
            print(0)
            return
        }
        _ = getMaxSumToLeaves(node: root, sum: 0)
        print(bestSum ?? 0)
    }
}

Amazon

Frage im Vorstellungsgespräch bei Amazon

Antwort im Vorstellungsgespräch

Beobachtete Unternehmen

Jobsuchen