104.二叉樹的最大深度
遞歸後序
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def getDepth(root):
if not root:
return 0
depth = 0
leftdepth = getDepth(root.left)# 左
rightdepth = getDepth(root.right)# 右
depth = max(leftdepth, rightdepth) + 1# 中 算上本層的結點 是以加1
return depth
if not root:
return 0
d =getDepth(root)
return d
疊代法
# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
que = deque([root])
k = 0 # 記錄周遊的層數
while que:
r = []
size = len(que)
for i in range(size):
cur = que.popleft()
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
k+=1
return k
559.n叉樹的最大深度
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def maxDepth(self, root: 'Node') -> int:
def getDepth(root):
if not root:
return 0
depth = 0
# 參考後序左右中 是以n叉樹 孩子周遊也是左右中 同時每次與上一次的
for child in root.children:
depth = max(depth,getDepth(child))
depth += 1 # 中
return depth
if not root:
return 0
d = getDepth(root)
return d
疊代法
"""
# Definition for a Node.
class Node(object):
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution(object):
def maxDepth(self, root):
"""
:type root: Node
:rtype: int
"""
if not root:
return 0
que = deque([root])
d = 0
while que:
size = len(que)
d+=1
for _ in range(size):
cur = que.popleft()
if cur.children:# 孩子不空
que.extend(cur.children)
return d
111.二叉樹的最小深度
遞歸
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def getDepth(root):
if not root:
return 0
leftdepth = getDepth(root.left)
rightdepth = getDepth(root.right)
#左孩空 右不為空，這時并不是最低點
if not root.left and root.right:
return rightdepth + 1
# 右孩空 左不為空，這時并不是最低點
elif root.left and not root.right:
return leftdepth + 1
depth = 1 + min(leftdepth,rightdepth)
return depth
if not root:
return 0
return getDepth(root)
疊代
# 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 minDepth(self, root: TreeNode) -> int:
if not root:
return 0
k = 1 # 根節點深度1
que = deque([(root,1)])
while que:
size = len(que)
for i in range(size):
cur,k = que.popleft()
# 假設是根節點 左右孩子都空 則傳回k
if cur.left == None and cur.right == None:
return k
# 因為在一個for循環内 有左還右孩子 層數都加1
if cur.left:
que.append((cur.left,k+1))
if cur.right:
que.append((cur.right,k+1))
return 0
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
que = deque()
que.append(root)
res = 1
while que:
for _ in range(len(que)):
node = que.popleft()
# 當左右孩子都為空的時候，說明是最低點的一層了，退出
if not node.left and not node.right:
return res
if node.left is not None:
que.append(node.left)
if node.right is not None:
que.append(node.right)
res += 1
return res
222. 完全二叉樹的節點個數
疊代法
# 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 countNodes(self, root: TreeNode) -> int:
if not root:
return 0
num = 0
que = deque([root])
while que:
size = len(que)
for _ in range (size):
num += 1
cur = que.popleft()
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
return num
遞歸法
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def countNodes(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def getNode(root):
if not root:
return 0
leftnum = getNode(root.left) # 左
rightnum = getNode(root.right) # 右
num = leftnum + rightnum + 1 #中
return num
return getNode(root)
110.平衡二叉樹
二叉樹節點的
深度
：指從根節點到該節點的最長簡單路徑邊的條數。（往下數在第幾層）
二叉樹節點的
高度
：指從該節點到
葉子節點
的最長簡單路徑邊的條數（往上數在第幾層）
因為求
深度
可以
從上到下
去查 是以需要
前序
周遊（中左右），而高度隻能
從下到上
去查，是以隻能
後序
周遊（左右中）
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if self.getHeight(root) != -1:
return True
else:
return False
def getHeight(self, root):
if not root: # 為空 高度0
return 0
lh = self.getHeight(root.left)# 左
if lh == -1:
return -1
rh = self.getHeight(root.right)# 右
if rh == -1:
return -1
if abs(lh - rh) > 1:#中
return -1
# 以目前節點為根節點的樹的最大高度 因為需要算上目前結點的高度
else:
return 1 + max(lh, rh)
257. 二叉樹的所有路徑
注：回溯和遞歸是一一對應的，有一個遞歸，就要有一個回溯
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
if not root:
return[]
res = []
self.getPath(root,'', res)
return res
def getPath(self, root, path, res):
if not root:
return
path += str(root.val) #中
# 處理單層邏輯 如果到葉子節點 加入清單中
if not root.left and not root.right:
res.append(path)
else:
path += '->'
self.getPath(root.left, path, res)#左
self.getPath(root.right, path, res)#右
404. 左葉子之和
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def sumOfLeftLeaves(self, root):
"""
:type root: TreeNode
:rtype: int
"""
# 邊界
if not root:
return 0
cur_val = 0
left_sum = self.sumOfLeftLeaves(root.left)# 左
right_sum = self.sumOfLeftLeaves(root.right)# 右
# 中 處理單層邏輯 判斷是不是左葉子 首先是左然後是葉子
if root.left != None and root.left.left == None and root.left.right == None:
cur_val = root.left.val
return cur_val + left_sum + right_sum
513.找樹左下角的值
思路：層序周遊 在樹的最後一行找到最左邊的值。