【Leetcode-94】
一、题目：二叉树的中序遍历
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
二、代码：
""" 代码1 """ # 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: TreeNode) -> List[int]: res = [] def travel(root): if not root: return travel(root.left) res.append(root.val) travel(root.right) travel(root) return res """ 代码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 inorderTraversal(self, root: TreeNode) -> List[int]: res = [] if root is None: return res stack = [] stack.append((root, 1)) while len(stack) > 0: node = stack.pop() if node[1] == 0: res.append(node[0].val) else: if node[0].right: stack.append((node[0].right, 1)) stack.append((node[0], 0)) if node[0].left: stack.append((node[0].left, 1)) return res
【Leetcode-98】
一、题目验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
二、代码：
# 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 isValidBST(self, root: TreeNode) -> bool: def judge(root, min_value=float('-inf'), max_value=float('inf')): if not root: return True val = root.val if min_value < val < max_value and judge(root.left, min_value=min_value, max_value=val) and judge(root.right, min_value=val, max_value=max_value): return True return False res = judge(root) return res
【Leetcode-101】
一、题目：对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
二、代码：
# 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: TreeNode) -> bool: def judge(root1, root2): if not root1 and not root2: return True if not (root1 and root2): return False if root1.val == root2.val and judge(root1.left, root2.right) and judge(root1.right, root2.left): return True return False res = judge(root.left, root.right) return res
【Leetcode-102】
一、题目：
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
二、代码：
# 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 levelOrder(self, root: TreeNode) -> List[List[int]]: res = [] if not root: return res que = [] que.append(root) num = len(que) while que: item = [] for i in range(num): node = que.pop(0) item.append(node.val) if node.left: que.append(node.left) if node.right: que.append(node.right) res.append(item) num = len(que) return res
【Leetcode-103】
一、题目：二叉树的锯齿形层序遍历
二、代码：
# 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 zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]: res = [] if not root: return res que = [] que.append(root) flag = 1 while len(que) > 0: res_item = [] for _ in range(len(que)): node = que.pop(0) res_item.append(node.val) if node.left: que.append(node.left) if node.right: que.append(node.right) if flag > 0: res.append(res_item) else: res.append(res_item[::-1]) flag = -flag return res
【Leetcode-104】
一、题目：二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
二、代码：
# 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: TreeNode) -> int: def get_depth(root): if not root: return 0 return 1 + max(get_depth(root.left), get_depth(root.right)) return get_depth(root)
【Leetcode-105】
一、题目：从前序和中序遍历构造二叉树
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
二、代码：
# 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: def build(pre, middle): if len(pre) == 0: return None root = TreeNode(pre[0]) root_index = middle.index(pre[0]) left = build(pre[1:root_index+1], middle[:root_index]) right = build(pre[root_index+1:], middle[root_index+1:]) root.left = left root.right = right return root return build(preorder, inorder)
【Leetcode-114】
一、题目：二叉树展开为链表
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
二、代码：
def flatten(self, root: TreeNode) -> None: """ Do not return anything, modify root in-place instead. """ res = [] if root is None: return res pre_node = p = TreeNode(0) stack = [] stack.append((root, 1)) while len(stack) > 0: node = stack.pop() if node[1] == 0: node[0].left = None p.right = node[0] p = p.right else: if node[0].right: stack.append((node[0].right, 1)) if node[0].left: stack.append((node[0].left, 1)) stack.append((node[0], 0)) return pre_node.right
【Leetcode-124】
一、题目：二叉树中的最大路径和
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 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 __init__(self) -> None: self.max_path_val = float('-inf') def maxPathSum(self, root: TreeNode) -> int: def max_provide(root): if not root: return 0 left_provide = max_provide(root.left) right_provide = max_provide(root.right) this_val = root.val path_val = left_provide + right_provide + this_val self.max_path_val = max(self.max_path_val, path_val) this_provide = this_val + max(left_provide, right_provide) return max(this_provide, 0) max_provide(root) return self.max_path_val
【Leetcode-199】
一、题目：二叉树的右视图
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
二、代码：
def rightSideView(self, root: TreeNode) -> List[int]: """ 层次遍历，每次的最后一个元素为右视图的元素 """ res = [] if not root: return res que = [root] while que: num = len(que) for i in range(num): node = que.pop(0) if i == num-1: res.append(node.val) if node.left: que.append(node.left) if node.right: que.append(node.right) return res
【Leetcode-230】
一、题目：二叉搜索树中第K小的元素
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
二、代码：
def kthSmallest(self, root: TreeNode, k: int) -> int: """ 中序遍历是有序的，遍历到第k个时返回 """ stack = [[root, 0]] cnt = 0 while len(stack) > 0: node, color = stack.pop() if color == 1: cnt += 1 if k == cnt: return node.val else: if node.right: stack.append([node.right, 0]) stack.append([node, 1]) if node.left: stack.append([node.left, 0])
【Leetcode-337】
一、题目：打家劫舍3
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
二、代码：
# 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 rob(self, root: TreeNode) -> int: """ 每个结点都有偷和不偷两种方式，分别计算两种方式下的收益 0表示不偷，1表示偷 """ def get_val(root): # 返回root结点能获得的收益 if not root: return [0, 0] left_val = get_val(root.left) right_val = get_val(root.right) val1 = max(left_val[0], left_val[1]) + max(right_val[0], right_val[1]) # 根节点不偷，左右可偷可不偷 val2 = root.val + left_val[0] + right_val[0] return [val1, val2] val = get_val(root) return max(val[1], val[0])
【Leetcode-437】
一、题目：路径总和
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
二、代码：
# 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 __init__(self) -> None: self.res_num = 0 def pathSum(self, root: TreeNode, sum1: int) -> int: """ 前缀和 """ def find_preval(root, cur_sum, target): # 计算前缀和 if not root: return this_sum = cur_sum + root.val this_cnt = look.get(this_sum - target, 0) self.res_num += this_cnt if this_sum not in look: look[this_sum] = 0 look[this_sum] += 1 find_preval(root.left, this_sum, target) find_preval(root.right, this_sum, target) look[this_sum] -= 1 # 调用 # 要遍历的结点/上面传下来的和/目标 look = {0:1} # 和为k的种类数 find_preval(root, 0, sum1) return self.res_num
【Leetcode-538】
一、题目：把二叉搜索树转为二叉累加树
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。
二、代码：
# 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 __init__(self) -> None: self.all_sum = 0 def convertBST(self, root: TreeNode) -> TreeNode: """ 反中序遍历，得到累加和 """ if not root: return self.convertBST(root.right) self.all_sum += root.val root.val = self.all_sum self.convertBST(root.left) return root
【Leetcode-617】
一、题目：合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
二、代码：
# 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 mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode: if not root1 and not root2: return None if not root1: return root2 elif not root2: return root1 left = self.mergeTrees(root1.left, root2.left) right = self.mergeTrees(root1.right, root2.right) root = TreeNode(root1.val+root2.val) root.left = left root.right = right return root
【Leetcode-814】
一、题目：二叉树剪枝
给定二叉树根结点 root ，此外树的每个结点的值要么是 0，要么是 1。
返回移除了所有不包含 1 的子树的原二叉树。
( 节点 X 的子树为 X 本身，以及所有 X 的后代。)
二、代码：
# 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 pruneTree(self, root: TreeNode) -> TreeNode: def contain_one(root): # 该子树是否包含1 if not root: return None left_judge = contain_one(root.left) right_judge = contain_one(root.right) root.left = root.left if left_judge else None root.right = root.right if right_judge else None if root.val == 1 or left_judge or right_judge: return root return None return contain_one(root)
【Leetcode-863】
一、题目：二叉树中所有距离为K的节点
给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。
返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。
二、代码：
def distanceK(self, root: TreeNode, target: TreeNode, K: int) -> List[int]: """ 1.将target作为root，算第0层，那么第k层即为要求的节点 2.为target作为root，需要指向其祖先节点，作为其儿子 3.指向祖先节点后，不能target到祖先再祖先到target，需要个set记录是否已经遍历 """ def set_parent(root, parent): if not root: # 已经到target，不必为其他节点增加parent,但无法检查是否有parent字段，因此都加 return root.parent = parent if root.left: set_parent(root.left, root) if root.right: set_parent(root.right, root) if not root: return [] set_parent(root, None) que = [target] visted = set() visted.add(target) level = 0 while len(que) > 0: res = [] for _ in range(len(que)): node = que.pop(0) res.append(node.val) if node.left and node.left not in visted: que.append(node.left) visted.add(node.left) if node.right and node.right not in visted: que.append(node.right) visted.add(node.right) if node.parent and node.parent not in visted: que.append(node.parent) visted.add(node.parent) if level == K: return res level += 1 return []
【Leetcode-958】
一、题目：二叉树的完全性检验
给定一个二叉树，确定它是否是一个完全二叉树。
百度百科中对完全二叉树的定义如下：
若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1~ 2h 个节点。）
二、代码：
def isCompleteTree(self, root: TreeNode) -> bool: """ 1.给每个节点赋值，层次遍历，从1开始，从上到下从左到右，如果为完全二叉树，那么node值为i时，两个孩子节点值分别为2*i和2*i+1 2.检查最后一个节点的值是否为节点总数即可判断是否时完全二叉树 3.如果某节点有右孩子但没左孩子肯定不是完全二叉树，可以终止计数 """ if not root: return True que = [(root, 1)] node_len = 0 last_val = -1 while que: for _ in range(len(que)): node, val = que.pop(0) if node: # 空节点会进队列，但不能算最后一个节点的值 if node.right and not root.left: return False last_val = val node_len += 1 que.append((node.left, 2*val)) que.append((node.right, 2*val+1)) if node_len == last_val: return True else: return False