思想

二叉樹的核心思想是分治和遞歸毫深，特點(diǎn)是遍歷方式坡疼。
解題方式常見兩類思路：

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

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

1. 前序是在剛剛進(jìn)入二叉樹節(jié)點(diǎn)時(shí)執(zhí)行；
2. 后序是在將要離開二叉樹節(jié)點(diǎn)時(shí)執(zhí)行务嫡；
3. 中序是左子樹遍歷完進(jìn)入右子樹前執(zhí)行甲抖；

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

多叉樹只有前后序列遍歷，因?yàn)橹挥卸鏄溆形ㄒ灰淮沃虚g節(jié)點(diǎn)的遍歷

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

實(shí)例

二叉樹中的最大路徑和 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é)點(diǎn)

輸出：
int去扣，返回二叉樹中的最大路徑和柱衔，路徑是指從樹中任意節(jié)點(diǎn)出發(fā)，沿父-子節(jié)點(diǎn)連接愉棱，達(dá)到任意節(jié)點(diǎn)的序列唆铐，且同一個(gè)節(jié)點(diǎn)在同一路徑中至多出現(xiàn)一次。路徑和指的是路徑中各個(gè)節(jié)點(diǎn)值的總和奔滑。

舉例：
給定二叉樹 [-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
要注意艾岂，最大路徑和不一定是最長(zhǎng)路徑，例如上面的最大路徑和是 15 + 20 + 7 = 42朋其。

二叉樹的數(shù)據(jù)存儲(chǔ)可以使用鏈表王浴，也可以使用數(shù)組，往往數(shù)組更容易表達(dá)梅猿，根節(jié)點(diǎn)從 index=1 處開始存儲(chǔ)氓辣，浪費(fèi) index=0 的位置
left_child = 2 * parent
right_child = 2 * parent + 1
parent = child // 2

  -10
  / \
 9  20
    / \
   15   7

分治解

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

1. 左右子樹的最大路徑和都小于 0筛婉，這時(shí)只取根節(jié)點(diǎn)簇爆，是最大路徑和癞松；
2. 左子樹的最大路徑和小于 0，此時(shí)最大路徑和的路徑是：根節(jié)點(diǎn) + 右子樹的最大路徑和所經(jīng)過的路徑入蛆；
3. 右子樹的最大路徑和小于 0响蓉，此時(shí)最大路徑和的路徑是：根節(jié)點(diǎn) + 左子樹的最大路徑和所經(jīng)過的路徑；

上例來看：

• 從根節(jié)點(diǎn) -10 出發(fā)哨毁，左子樹最大路徑和是 9枫甲，右子樹是 20 + 15 = 35，當(dāng)下最大路徑和是 -10 + 9 + 35 = 34；
• -10.left=9想幻，從 9 出發(fā)粱栖，左右子樹都是空，所以當(dāng)下最大路徑和是 9脏毯；
• -10.right=20闹究，從 20 出發(fā)，左子樹最大路徑和是 15食店，右子樹最大路徑和是 7渣淤，當(dāng)下最大路徑和是 15 + 20 + 7 = 42；
• 20.left=15吉嫩，從 15 出發(fā)价认，左右子樹都是空，所以當(dāng)下最大路徑和是 15自娩；
• 20.right=7用踩，從 7 出發(fā)，左右子樹都是空忙迁，所以當(dāng)下最大路徑和是 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:
        # 初始條件，空時(shí)返回 0
        if root is None:
            return 0
        # 判斷左右子樹最大值动漾，如果小于 0 則路徑不選擇左右子樹的節(jié)點(diǎn)
        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)
        # 返回當(dāng)前遍歷的最大值丁屎，一定包含 root 節(jié)點(diǎn)，并選擇左右子樹較大的一個(gè)
        return root.val + max(left_max, right_max)

    max_path_sum(root)
    return max_sum

相關(guān)

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