思想

二叉樹的核心思想是分治和遞歸，特點是遍歷方式。
解題方式常見兩類思路：

1. 遍歷一遍二叉樹尋找答案；
2. 通過分治分解問題尋求答案；

遍歷分為前中后序，本質(zhì)上是遍歷二叉樹過程中處理每個節(jié)點的三個特殊時間點：

1. 前序是在剛剛進入二叉樹節(jié)點時執(zhí)行；
2. 后序是在將要離開二叉樹節(jié)點時執(zhí)行；
3. 中序是左子樹遍歷完進入右子樹前執(zhí)行；

# 前序
     1 node
    /      \
 2 left   3 right
中左右
 
# 中序
     2 node
    /      \
 1 left    3 right
左中右
 
# 后序
     3 node
    /      \
 1 left    2 right     
左右中       

多叉樹只有前后序列遍歷，因為只有二叉樹有唯一一次中間節(jié)點的遍歷

題目的關(guān)鍵就是找到遍歷過程中的位置，插入對應(yīng)代碼邏輯實現(xiàn)場景的目的。

實例

二叉樹中的最大路徑和 leetcode 124

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

輸入：
root: TreeNode，二叉樹的根節(jié)點

輸出：
int，返回二叉樹中的最大路徑和，路徑是指從樹中任意節(jié)點出發(fā)，沿父-子節(jié)點連接，達到任意節(jié)點的序列，且同一個節(jié)點在同一路徑中至多出現(xiàn)一次。路徑和指的是路徑中各個節(jié)點值的總和。

舉例：
給定二叉樹 [-10,9,20,null,null,15,7]
路徑包括:
9
9 -> -10
9 -> -10 -> 20
9 -> -10 -> 20 -> 7
9 -> -10 -> 20 -> 15
-10
-10 -> 20
-10 -> 20 -> 15
-10 -> 20 -> 7
20
20 -> 15
20 -> 7
15
15 -> 20 -> 7
要注意，最大路徑和不一定是最長路徑，例如上面的最大路徑和是 15 + 20 + 7 = 42。

二叉樹的數(shù)據(jù)存儲可以使用鏈表，也可以使用數(shù)組，往往數(shù)組更容易表達，根節(jié)點從 index=1 處開始存儲，浪費 index=0 的位置
left_child = 2 * parent
right_child = 2 * parent + 1
parent = child // 2

  -10
  / \
 9  20
    / \
   15   7

分治解

從根節(jié)點開始，先簡化問題，有三種路徑形成方式：

1. 左右子樹的最大路徑和都小于 0，這時只取根節(jié)點，是最大路徑和；
2. 左子樹的最大路徑和小于 0，此時最大路徑和的路徑是：根節(jié)點 + 右子樹的最大路徑和所經(jīng)過的路徑；
3. 右子樹的最大路徑和小于 0，此時最大路徑和的路徑是：根節(jié)點 + 左子樹的最大路徑和所經(jīng)過的路徑；

上例來看：

• 從根節(jié)點 -10 出發(fā)，左子樹最大路徑和是 9，右子樹是 20 + 15 = 35，當下最大路徑和是 -10 + 9 + 35 = 34；
• -10.left=9，從 9 出發(fā)，左右子樹都是空，所以當下最大路徑和是 9；
• -10.right=20，從 20 出發(fā)，左子樹最大路徑和是 15，右子樹最大路徑和是 7，當下最大路徑和是 15 + 20 + 7 = 42；
• 20.left=15，從 15 出發(fā)，左右子樹都是空，所以當下最大路徑和是 15；
• 20.right=7，從 7 出發(fā)，左右子樹都是空，所以當下最大路徑和是 7；

全局最大路徑和是 42

編碼

from typing import Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def binary_tree_maximum_path_sum(root: Optional[TreeNode]) -> int:
    max_sum  = None

    def max_path_sum(root: Optional[TreeNode]) -> int:
        # 初始條件，空時返回 0
        if root is None:
            return 0
        # 判斷左右子樹最大值，如果小于 0 則路徑不選擇左右子樹的節(jié)點
        left_max = max(0, max_path_sum(root.left))
        right_max = max(0, max_path_sum(root.right))
        # 更新全局最大值
        nonlocal max_sum
        if max_sum is None:
            max_sum = root.val + left_max + right_max
        else:
            max_sum = max(root.val + left_max + right_max, max_sum)
        # 返回當前遍歷的最大值，一定包含 root 節(jié)點，并選擇左右子樹較大的一個
        return root.val + max(left_max, right_max)

    max_path_sum(root)
    return max_sum

相關(guān)

二叉樹 0
二叉樹 1
二叉樹 2
二叉樹 3
二叉樹 4
二叉樹 5