上一題有路徑有關(guān)熟空，難度稍大。現(xiàn)在看個比較簡單的題目鼠次。
題目：計算二叉樹路徑之和的最大值。
二叉樹節(jié)點可以表示為：
private class BinaryTreeNode {
int value;
BinaryTreeNode left;
BinaryTreeNode right;
}
雖然也涉及到了路徑芋齿，但是并不要求記錄具體路徑節(jié)點腥寇。
public int maxPathSum(BinaryTreeNode root) {
if (root == null) {
return 0;
}
int childMax = Math.max(maxPathSum(root.left), maxPathSum(root.right));
return root.value + childMax;
}
算法是二叉樹遞歸中的后序遍歷。與之類似的題目是求二叉樹的高度觅捆，相當(dāng)于是特殊情況赦役。
public int height(BinaryTreeNode root) {
if (root == null) {
return 0;
}
int childMaxHeight = Math.max(height(root.left), height(root.right));
return childMaxHeight + 1;
}
