二叉树的遍历
- 按照根节点的访问顺序分为前序、中序和后序遍历
- 遍历二叉树的时间复杂度为O(n)，空间复杂度为O(h)
- 二叉树剪枝：https://leetcode.cn/problems/pOCWxh/
class Solution:
def pruneTree(self, root: TreeNode) -> TreeNode:
if root is None:
return None
root.left = self.pruneTree(root.left)
root.right = self.pruneTree(root.right)
if root.left is None and root.right is None and root.val == 0:
return None
else:
return root- 序列化与反序列化二叉树:
def dfs(s, idx):
if not s:
return None
if idx[0] >= len(s):
return None
if s[idx[0]] == "#":
idx[0] = 1
return None
node = TreeNode(s[idx[0]])
idx[0] = 1
node.left = dfs(s, idx)
node.right = dfs(s, idx)
return node
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
if root is None:
return "#"
c = str(root.val)
lc = self.serialize(root.left)
rc = self.serialize(root.right)
return f'{c},{lc},{rc}'
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
s = data.split(',')
return dfs(s, [0])二叉搜索树
- 它是一棵二叉树，其中每个节点都满足以下性质：左子树中的所有节点的值都小于该节点的值，右子树中的所有节点的值都大于该节点的值。
- 对于任意节点，其左右子树也都是都是二叉搜索树。
- 寻找二叉搜索树中的目标节点
Link: https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/description/
代码语言：javascript复制def dfs(node, heap, cnt):
if node is None:
return
dfs(node.right, heap, cnt)
heap.append(node.val)
if len(heap) == cnt:
return
dfs(node.left, heap, cnt)
class Solution:
def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:
heap = []
dfs(root, heap, cnt)
return heap[cnt - 1]- 二叉搜索树中两个节点之和：
Link: https://leetcode.cn/problems/opLdQZ/description/
代码语言：javascript复制class Solution:
def findTarget(self, root: TreeNode, k: int) -> bool:
def dfs(node, m, k):
if node is None:
return
if k - node.val in m:
self.res = True
return
m[node.val] = True
dfs(node.left, m, k)
dfs(node.right, m, k)
m = {}
self.res = False
dfs(root, m, k)
return self.res
