543. Diameter of Binary Tree

Question: Diameter of Binary Tree

Solution1 bottom up DFS

想法：

bottom up to avoid duplicated work

計算每個 node 的 diameter，就是把「左邊最大高度」跟「右邊最大高度」相加，所以要回傳 node 的最大高度，之後只要往上累加就可以囉！

1. 設定一個全域變數，用來存 DFS 時找到的最大 diameter: res = [0]
2. 寫一個 recursive function 用來查找 node 的最大高度，高度為自己的高度 1 加上左邊高度或右邊高度，取較大者: def get_height(node) return 1 + max(left_height, right_height)
   1. 如果 node == None: return -1 (方便在數學上的計算)
   2. 呼叫自己，回傳左邊高度: left_height = get_height(node.left)
   3. 呼叫自己，回傳右邊高度: right_height = get_height(node.right)
   4. 計算 diameter = 左邊最大高度 + 右邊最大高度 + 2
   5. 比較 res 與 diameter，較大的值存起來
   6. return node 本身的最大高度: 1 + max(left_height, right_height)
3. 呼叫 get_height(root)
4. return res 值

Time complexity: O(n)

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution:

def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:

res = [0]

def get_height(node):

if node == None:

return -1

left_height = get_height(node.left)

right_height = get_height(node.right)

diameter = left_height + right_height + 2

res[0] = max(res[0], diameter)

height = 1 + max(left_height, right_height)

return height

get_height(root)

return res[0]

Video Solution