https://zhuanlan.zhihu.com/p/29800274
是否對稱樹
# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
def isSym(left,right):
if not left and not right: return True
if not left and right: return False
if left and not right: return False
if left.val !=right.val:return False
return isSym(left.left,right.right) and isSym(left.right,right.left)
if not root:
return True
return isSym(root.left,root.right)
是否相同
# 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 isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if p is None and q is not None: return False
if p is None and q is None: return True
if p is not None and q is None: return False
if p.val != q.val:
return False
return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
中序遍歷
# 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
def inorder(root):
if root:
inorder(root.left)
result.append(root.val)
inorder(root.right)
inorder(root)
return result
二叉樹的最大深度
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return max(self.maxDepth(root.left),self.maxDepth(root.right)) + 1
求二叉樹節(jié)點(diǎn)個(gè)數(shù)
def treeNodenums(node):
if node is None:
return 0
nums = treeNodenums(node.left)
nums += treeNodenums(node.right)
return nums + 1
二叉樹的層序遍歷
輸入：root = [3,9,20,null,null,15,7]
輸出：[[3],[9,20],[15,7]]
#二叉樹
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
queue = []
queue.append(root)
res = []
while queue:
ll = []
for i in range(len(queue)):
q = queue.pop(0)
ll.append(q.val)
if q.left:
queue.append(q.left)
if q.right:
queue.append(q.right)
res.append(ll)
return res
二叉樹的鋸齒形遍歷
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
queue = []
queue.append(root)
res = []
event = False
while queue:
ll = []
for i in range(len(queue)):
q = queue.pop(0)
ll.append(q.val)
if q.left:
queue.append(q.left)
if q.right:
queue.append(q.right)
res.append(ll[::-1] if event else ll)
event = not event
return res
找樹最后一層，最左的值
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
queue = []
queue.append(root)
while queue:
q = queue.pop(0)
if q and q.right:
queue.append(q.right)
if q and q.left:
queue.append(q.left)
return q.val
In [7]: a =[1,2]
In [8]: for i in range(len(a)):
...: print("len:",len(a)," ",a[i])
...: a.append(3)
...:
...:
len: 2 1
len: 3 2
前序與中序遍歷序列構(gòu)造二叉樹
# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if inorder:
# 獲取根節(jié)點(diǎn)
idx = inorder.index(preorder.pop(0))
root = TreeNode(inorder[idx])
# 通過中序遍歷將二叉樹的左右節(jié)點(diǎn)分開，中序遍歷的左邊為左節(jié)點(diǎn)，右邊為右節(jié)點(diǎn)
root.left = self.buildTree(preorder, inorder[0:idx])
root.right = self.buildTree(preorder, inorder[idx+1:])
return root
從中序與后序遍歷序列構(gòu)造二叉樹
# 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 buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
if inorder:
val = postorder[-1]
n = inorder.index(val)
root = TreeNode(val)
root.left = self.buildTree(inorder[0:n],postorder[0:n])
root.right = self.buildTree(inorder[n+1:],postorder[n:-1])
return root
# val = postorder[-1]
# n = inorder.index(val)
# root = TreeNode(val)#創(chuàng)建樹
# root.left = self.buildTree(inorder[:n],postorder[:n])
# root.right = self.buildTree(inorder[n+1:],postorder[n:-1])
# return root
翻轉(zhuǎn)二叉樹
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if root:
rmp = root.left
root.left=root.right
root.right=rmp
self.invertTree(root.left)
self.invertTree(root.right)
return root
二叉樹的最小深度
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root: return 0
stack, ans = deque([root]), 1
while stack:
node_num = len(stack)
for _ in range(node_num):
node = stack.popleft()
if not node.left and not node.right:
return ans
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
ans += 1
class Solution(object):
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root == None:
return 0
if root.left != None and root.right == None:
return self.minDepth(root.left)+1
if root.left == None and root.right != None:
return self.minDepth(root.right)+1
return min(self.minDepth(root.left),self.minDepth(root.right))+1
199. 二叉樹的右視圖
def rightSideView(root) -> List[int]:
ans = []
def f(node, depth):
if node is None:
return
if len(ans) == depth:
ans.append(node.val)
f(root.right, depth + 1)
f(root.left, depth + 1)
f(root, 0)
return ans
# 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 rightSideView(self, root: TreeNode) -> List[int]:
if root == None:
return []
# 初始化隊(duì)列和結(jié)果
queue = [root]
res = []
# 當(dāng)隊(duì)列不為空
while queue:
# 當(dāng)前層的節(jié)點(diǎn)數(shù)
size = len(queue)
# 彈出當(dāng)前層的所有節(jié)點(diǎn)
for i in range(size):
node = queue.pop(0)
# 如果節(jié)點(diǎn)是當(dāng)前層的最后一個(gè)，則入 res
if(i == size - 1):
res.append(node.val)
# 將當(dāng)前層的所有節(jié)點(diǎn)入隊(duì)列
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return res
判斷一顆二叉樹是否是“高度”平衡的。
平衡二叉樹的定義是二叉樹的任意節(jié)點(diǎn)的兩顆子樹之間的高度差小于等于1。
class Solution(object):
def maxDepth(self, root):
if root == None:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right))+1
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root == None:
return True
if abs(self.maxDepth(root.left) - self.maxDepth(root.right)) > 1:
return False
return self.isBalanced(root.left) and self.isBalanced(root.right)
236. 二叉樹的最近公共祖先
class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
if not root or root == p or root == q: return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if not left and not right: return # 1.
if not left: return right # 3.
if not right: return left # 4.
return root # 2. if left and right:
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def lowestCommonAncestor(root, p, q):
if not root or root == p or root == q:
return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left or right
617. 合并二叉樹
class Solution:
def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
if not t1:
return t2
if not t2:
return t1
merged = TreeNode(t1.val + t2.val)
merged.left = self.mergeTrees(t1.left, t2.left)
merged.right = self.mergeTrees(t1.right, t2.right)
return merged
669. 修剪二叉搜索樹
給你二叉搜索樹的根節(jié)點(diǎn) root ，同時(shí)給定最小邊界low 和最大邊界 high。通過修剪二叉搜索樹，使得所有節(jié)點(diǎn)的值在[low, high]中。修剪樹 不應(yīng)該 改變保留在樹中的元素的相對結(jié)構(gòu) (即，如果沒有被移除，原有的父代子代關(guān)系都應(yīng)當(dāng)保留)。
class Solution:
def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
if not root: return root
# 如果根節(jié)點(diǎn)的值不滿足最小邊界，那么返回剪枝后的右子樹，同理不滿足最大邊界，返回剪枝后的左子樹
if root.val < low: return self.trimBST(root.right, low, high)
if root.val > high: return self.trimBST(root.left, low, high)
# 如果根節(jié)點(diǎn)滿足邊界值，那么只需要修剪左右子樹即可
root.left = self.trimBST(root.left, low, high)
root.right = self.trimBST(root.right, low, high)
return root
814. 二叉樹剪枝
給你二叉樹的根結(jié)點(diǎn) root ，此外樹的每個(gè)結(jié)點(diǎn)的值要么是 0 ，要么是 1 。
返回移除了所有不包含 1 的子樹的原二叉樹。
節(jié)點(diǎn) node 的子樹為 node 本身加上所有 node 的后代。
class Solution:
def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def dfs(root):
if not root: return None
# 如果沒有左右子節(jié)點(diǎn)，說明該結(jié)點(diǎn)是葉子結(jié)點(diǎn)，并且值為0，那么刪除即可
if not root.left and not root.right and root.val == 0:
return None
left = dfs(root.left)
right = dfs(root.right)
# 如果沒有左右子樹，說明可能左右子樹都被剪枝了，這個(gè)時(shí)候如果root值為0，那么刪除即可
if not left and not right and root.val == 0:
return None
# 更新左右子樹的值
root.left = left
root.right = right
return root
# 返回新的剪枝結(jié)果
return dfs(root)
662. 二叉樹最大寬度
class Solution:
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
res = 1
q = [[root, 1]]
while q:
for i in range(len(q)):
node = q.pop(0)
if node[0].left:
q.append([node[0].left, node[1] * 2])
if node[0].right:
q.append([node[0].right, node[1] * 2 + 1])
if q:
res = max(res, q[-1][1] - q[0][1] + 1)
return res
257. 二叉樹的所有路徑
# 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 binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
def dfs(root,path,paths):
if root is None:
return
if root.left is None and root.right is None:
paths.append(path + str(root.val))
return
dfs(root.left, path + str(root.val) + "->" ,paths)
dfs(root.right, path + str(root.val) + "->" ,paths)
paths = []
dfs(root,"",paths)
return paths
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
if not root:
return []
def dfs(root,path,paths):
if root.left is None and root.right is None:
paths.append(path)
return
if root.left:
dfs(root.left, path + str(root.left.val) + "->" ,paths)
if root.right:
dfs(root.right, path + str(root.right.val) + "->" ,paths)
paths = []
dfs(root,str(root.val),paths)
return paths
二叉樹中和為某一值的路徑
def find_path(root, target):
paths = []
if not root:
return paths
def dfs(root, path, paths):
if not root.left and not root.right and sum(path) == target:
paths.append(path)
if root.left:
dfs(root.left, path + [root.left.val], paths)
if root.right:
dfs(root.right, path + [root.right.val], paths)
dfs(root, [root.val], paths)
return paths
二叉樹中的最大路徑和
我們現(xiàn)在要求最大路徑和，那么就要分別得到左右兩條路徑的最大和。而左路徑的最大和為左節(jié)點(diǎn)的值加上它左右路徑中較大的路徑和，右路徑最大和為右節(jié)點(diǎn)的值加上它左右路徑中較大的路徑和。
注意：如果某條子路徑的左右節(jié)點(diǎn)為負(fù)，直接置為0，等于不走這個(gè)節(jié)點(diǎn)。
class Solution(object):
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.maxSum = float('-inf')
self._maxPathSum(root)
return self.maxSum
def _maxPathSum(self, root): # DFS
if root is None:
return 0
left = self._maxPathSum(root.left)
right = self._maxPathSum(root.right)
left = left if left > 0 else 0
right = right if right > 0 else 0
self.maxSum = max(self.maxSum, root.val + left + right)
# print self.maxSum
return max(left, right) + root.val
將一個(gè)排序好的數(shù)組轉(zhuǎn)換為一顆二叉查找樹, 這顆二叉查找樹要求是平衡的。
def sortedArrayToBST(sort_arr):
length = len(sort_arr)
if length == 0:
return None
elif length == 1:
return TreeNode(sort_arr[0])
mid_index = length // 2 + 1
root_val = sort_arr[mid_index]
root = TreeNode(root_val)
root.left = sortedArrayToBST(sort_arr[:mid_index])
root.right = sortedArrayToBST(sort_arr[mid_index + 1:])
return root
將一個(gè)升序鏈表轉(zhuǎn)為有序二叉樹
def sortedListToBST(head):
def convert(head, tail):
if head == tail:
return None
if head.next == tail:
return TreeNode(head.val)
mid = head
fast = head
while fast != tail and fast.next != tail:
fast = fast.next.next
mid = mid.next
root = TreeNode(mid.val)
root.left = TreeNode(head, mid)
root.right = TreeNode(mid.next, tail)
return convert(head, None)
判斷一棵樹是否為[二叉搜索樹]
class Solution(object):
def inorderTraversal(self, root, inorder):
if root:
self.inorderTraversal(root.left, inorder)
inorder.append(root.val)
self.inorderTraversal(root.right, inorder)
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
# if not root.left or not root.right:
# return True
inorder = []
self.inorderTraversal(root, inorder)
for i in range(len(inorder)-1):
if inorder[i] >= inorder[i+1]:
return False
return True
class Solution(object):
flag = None
pre = -2147483649 # 有一個(gè)測試集是-2147483648
def inorderTraversal(self, root):
if root:
self.inorderTraversal(root.left)
if self.pre:
if self.pre > root.val:
self.flag = false
else:
self.pre = root.val:
self.pre = root.val
self.inorderTraversal(root.right)
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
# if not root.left or not root.right:
# return True
self.inorderTraversal(root)
return self.flag
要求所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)組成的數(shù)字的和。
一棵樹的每個(gè)節(jié)點(diǎn)都是0-9中的某一個(gè)數(shù)字，現(xiàn)在把從根節(jié)點(diǎn)到某一個(gè)葉子節(jié)點(diǎn)之間所有節(jié)點(diǎn)的數(shù)字依次連接起來組成一個(gè)新的數(shù)字。
class Solution(object):
def sumNumbers(self, root):
"""
:type root: TreeNode
:rtype: int
"""
return self._sumNumbers(root,0)
def _sumNumbers(self, root, preSum):
if not root:
return 0
preSum = preSum * 10 + root.val
if root.left == None and root.right == None:
return preSum
return self._sumNumbers(root.left, preSum) + self._sumNumbers(root.right, preSum)
二叉樹葉子結(jié)點(diǎn)的最大距離
def get_yznode_max_distance(root):
if not root:
return 0
def get_max_depth(root):
if not root:
return 0
return max(get_max_depth(root.left), get_max_depth(root.right)) + 1
depth_left = get_max_depth(root.left)
depth_right = get_max_depth(root.right)
return depth_left + depth_right + 1
