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
求二叉树节点个数
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
前序与中序遍历序列构造二叉树
# 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:
# 获取根节点
idx = inorder.index(preorder.pop(0))
root = TreeNode(inorder[idx])
# 通过中序遍历将二叉树的左右节点分开，中序遍历的左边为左节点，右边为右节点
root.left = self.buildTree(preorder, inorder[0:idx])
root.right = self.buildTree(preorder, inorder[idx+1:])
return 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 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)#创建树
# root.left = self.buildTree(inorder[:n],postorder[:n])
# root.right = self.buildTree(inorder[n+1:],postorder[n:-1])
# return root
翻转二叉树
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 []
# 初始化队列和结果
queue = [root]
res = []
# 当队列不为空
while queue:
# 当前层的节点数
size = len(queue)
# 弹出当前层的所有节点
for i in range(size):
node = queue.pop(0)
# 如果节点是当前层的最后一个，则入 res
if(i == size - 1):
res.append(node.val)
# 将当前层的所有节点入队列
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return res
判断一颗二叉树是否是“高度”平衡的。
平衡二叉树的定义是二叉树的任意节点的两颗子树之间的高度差小于等于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. 修剪二叉搜索树
给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。
class Solution:
def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
if not root: return root
# 如果根节点的值不满足最小边界，那么返回剪枝后的右子树，同理不满足最大边界，返回剪枝后的左子树
if root.val < low: return self.trimBST(root.right, low, high)
if root.val > high: return self.trimBST(root.left, low, high)
# 如果根节点满足边界值，那么只需要修剪左右子树即可
root.left = self.trimBST(root.left, low, high)
root.right = self.trimBST(root.right, low, high)
return root
814. 二叉树剪枝
给你二叉树的根结点 root ，此外树的每个结点的值要么是 0 ，要么是 1 。
返回移除了所有不包含 1 的子树的原二叉树。
节点 node 的子树为 node 本身加上所有 node 的后代。
class Solution:
def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def dfs(root):
if not root: return None
# 如果没有左右子节点，说明该结点是叶子结点，并且值为0，那么删除即可
if not root.left and not root.right and root.val == 0:
return None
left = dfs(root.left)
right = dfs(root.right)
# 如果没有左右子树，说明可能左右子树都被剪枝了，这个时候如果root值为0，那么删除即可
if not left and not right and root.val == 0:
return None
# 更新左右子树的值
root.left = left
root.right = right
return root
# 返回新的剪枝结果
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
二叉树中的最大路径和
我们现在要求最大路径和，那么就要分别得到左右两条路径的最大和。而左路径的最大和为左节点的值加上它左右路径中较大的路径和，右路径最大和为右节点的值加上它左右路径中较大的路径和。
注意：如果某条子路径的左右节点为负，直接置为0，等于不走这个节点。
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
将一个排序好的数组转换为一颗二叉查找树, 这颗二叉查找树要求是平衡的。
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
将一个升序链表转为有序二叉树
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 # 有一个测试集是-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
要求所有从根节点到叶子节点组成的数字的和。
一棵树的每个节点都是0-9中的某一个数字，现在把从根节点到某一个叶子节点之间所有节点的数字依次连接起来组成一个新的数字。
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)
二叉树叶子结点的最大距离
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
