- 1、二叉树的前序遍历
- 2、二叉树的中序遍历
- 3、二叉树的后序遍历
- 4、二叉树的层序遍历
- 5、按之字形顺序打印二叉树(有层,可以用这个来做有层的东西)
- 6、 二叉树的最大深度
- 7、二叉树中和为某一值的路径(一)找到就行 只输出true false
- 8、二叉树中和为某一值的路径(二) 返回具体的所有的路径
- 9、二叉树中和为某一值的路径(三)可以不从根开始
- 10、二叉搜索树与双向链表
- 11、对称的二叉树
- 12、 合并二叉树(节点值相加或者把新节点放上去)
- 13、二叉树的镜像
- 14、判断是不是二叉搜索树
- 15、判断是不是完全二叉树
- 16、判断是不是平衡二叉树
- 17、二叉搜索树的最近公共祖先(给节点上的值找祖先)
- 18、在二叉树中找到两个节点的最近公共祖先(给节点上的值找祖先)(不是二叉搜索树了)
- 19、序列化二叉树
- 20、重建二叉树
- 21、输出二叉树的右视图
class Solution:
def preorderTraversal(self , root: TreeNode) -> List[int]:
# write code here
res, tmp = [], []
cur = root# 借助一个指针
while cur or tmp:# 指针和tmp还不为none的时候
while cur:
res.append(cur.val)# res里把cur加进去
tmp.append(cur)# tmp用来存储剩下的东西的
cur = cur.left# 前序是根左右 所以先left 再right
cur = tmp.pop()# 把根d出去
cur = cur.right
return res
通用,但深度可能会超
class Solution:
def inorderTraversal(self , root: TreeNode) -> List[int]:
# write code here
# 根左右
def dfs(root):
if not root:
return
res.append(root.val)
dfs(root.left)
dfs(root.right)
res = []
dfs(root)
return res
2、二叉树的中序遍历
class Solution:
def inorderTraversal(self , root: TreeNode) -> List[int]:
# write code here
# 左根右
def dfs(root):
if not root:
return
dfs(root.left)
res.append(root.val)
dfs(root.right)
res = []
dfs(root)
return res
上面那个要是递归深度太大了,就可以换下面这个
class Solution:
def inorderTraversal(self , root: TreeNode) -> List[int]:
# write code here
ans = []
cur = root
while cur:
if cur.left:
pre = cur.left
while pre.right and pre.right != cur:
pre = pre.right
if pre.right:
pre.right = None
ans.append(cur.val)
cur = cur.right
else:
pre.right = cur
cur = cur.left
else:
ans.append(cur.val)
cur = cur.right
return ans
3、二叉树的后序遍历
class Solution:
def postorderTraversal(self , root: TreeNode) -> List[int]:
# write code here
# 左右根
def dfs(root):
if not root:
return
dfs(root.left)
dfs(root.right)
res.append(root.val)
res = []
dfs(root)
return res
通用,但深度可能会超
class Solution:
def inorderTraversal(self , root: TreeNode) -> List[int]:
# write code here
# 左右根
def dfs(root):
if not root:
return
dfs(root.left)
dfs(root.right)
res.append(root.val)
res = []
dfs(root)
return res
4、二叉树的层序遍历
class Solution:
def levelOrder(self , root: TreeNode) -> List[List[int]]:
# write code here
# 借助栈
if not root:
return []
res = []
queue = [root]
while queue:
tmp = []
for _ in range(len(queue)):
node = queue.pop(0)
tmp.append(node.val)# 这个tmp就有点类似之前的后序遍历了 先是上一层的根 在放左右子节点
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(tmp)
return res
5、按之字形顺序打印二叉树(有层,可以用这个来做有层的东西)
class Solution:
def Print(self , pRoot: TreeNode) -> List[List[int]]:
# write code here
#假设根节点为第一层,按照奇数层,从左到右打印,偶数层,从右到左打印
if not pRoot:return []
curLayer = [pRoot]# 第一层
res = []
cnt = 0# 这个是用来判断层的 下次遇到和层有关系的东西就用这个 这个可以调整层
while curLayer:# curLayer不空的时候(这个其实就是根
nextLayer = []
tmp = []
for node in curLayer:
tmp.append(node.val)
if node.left:# 左不空 叶子放进来
nextLayer.append(node.left)
if node.right:# 右不空
nextLayer.append(node.right)
if cnt == 0:# 判断是奇数还是偶数# 其实就只是从这里加了一步 和上面几乎一模一样
res.append(tmp)
else:
res.append(tmp[::-1])
curLayer = nextLayer# 挪到下一层
cnt = (cnt+1) % 2 # 创造奇偶条件
return res
6、 二叉树的最大深度
class Solution:
def maxDepth(self , root: TreeNode) -> int:
# write code here
if not root: return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
7、二叉树中和为某一值的路径(一)找到就行 只输出true false
class Solution:
def hasPathSum(self , root: TreeNode, s: int) -> bool:
# write code here
res=0
if not root:return False
res += root.val
if res==s and not root.left and not root.right:
return True
return self.hasPathSum(root.left, s-res) or self.hasPathSum(root.right, s-res)
8、二叉树中和为某一值的路径(二) 返回具体的所有的路径
class Solution:
def FindPath(self , root: TreeNode, target: int) -> List[List[int]]:
ret, path = [], []
def dfs(root: TreeNode, target: int):
# 处理树为空
if not root: return
# 路径更新
path.append(root.val)
# 更新
target -= root.val
# 如果递归当前节点为叶子节点且该条路径的值已经达到了expectNumber,则更新ret
if not root.left and not root.right and target == 0:
ret.append(path[:])
# 左右子树递归
dfs(root.left, target)
dfs(root.right, target)
path.pop()
dfs(root, target)
return ret
class Solution:
def FindPath(self , root: TreeNode, target: int) -> List[List[int]]:
if not root: return []
# 直接将所需要的节点,路径,节点值组成一个列表
s = [(root, [root.val], root.val)]
ret = []
while s:
node, val, sum = s.pop()
# 如果是到了叶子节点的情况下,并且路径总和与target一致
if node and not node.left and not node.right and sum == target:
ret.append(val)
# 处理左子树路径
if node.left:
s.append((node.left, val + [node.left.val], sum + node.left.val))
# 处理右子树路径
if node.right:
s.append((node.right, val + [node.right.val], sum + node.right.val))
return ret
上面两个是牛客给的,下面是视频学的
class Solution:
def FindPath(self , root: TreeNode, target: int) -> List[List[int]]:
# write code here
# 因为这道题都是按照根节点开始找路径 所以前序是必要的
# 因为需要输出所有可能性 所以要用一个列表来保存 不然 输出了 就找不到了
# 每一条路都遍历 走完 不合理的就回退一步 合理的就退到有另一条路的地方开始遍历
# 这个也可以看作是一个递归的过程
res=[]# 这个列表中用来存的也是列表 最后就返回这个大列表就可以了
path=[]# 每一次遍历记录路径
def find(root,target):
if root==None:
return
path.append(root.val)
target -= root.val
if target==0 and root.left==None and root.right==None:# 结果值相同了 并且没有更多的节点了
res.append(path[:])# 如果不这样加入的话 path会不断在改变 最终就是最后的结果输出很多次
find(root.left, target)
find(root.right, target)
path.pop()# 找完左右子树 就把根节点d出
find(root, target)
return res
9、二叉树中和为某一值的路径(三)可以不从根开始
class Solution:
def __init__(self):
self.res = 0
#dfs查询以某节点为根的路径数
def dfs(self, root: TreeNode, sum: int):
if root is None:
return
#符合目标值
if sum == root.val:
self.res += 1
#进入子节点继续找
self.dfs(root.left, sum - root.val)
self.dfs(root.right, sum - root.val)
def FindPath(self , root: TreeNode, sum: int) -> int:
#为空则返回
if root is None:
return self.res
#查询以某节点为根的路径数
self.dfs(root, sum)
#以其子节点为新根
self.FindPath(root.left, sum);
self.FindPath(root.right, sum)
return self.res
class Solution:
def __init__(self):
#记录路径和及条数
self.mp = dict()
#last为到上一层为止的累加和
def dfs(self, root: TreeNode, sum: int, last: int) -> int:
#空结点直接返回
if root is None:
return 0
res = 0
#到目前结点为止的累加和
temp = root.val + last;
#如果该累加和减去sum在哈希表中出现过,相当于减去前面的分支
if (temp - sum) in self.mp:
#加上有的路径数
res += self.mp[temp - sum]
#增加该次路径和
if temp in self.mp:
self.mp[temp] += 1
else:
self.mp[temp] = 1
#进入子结点
res += self.dfs(root.left, sum, temp)
res += self.dfs(root.right, sum, temp)
#回退该路径和,因为别的树枝不需要这边存的路径和
self.mp[temp] -= 1
return res
def FindPath(self , root: TreeNode, sum: int) -> int:
#路径和为0的有1条
self.mp[0] = 1
return self.dfs(root, sum, 0)
上面两个是牛客给的,下面是视频学的
class Solution:
def FindPath(self , root: TreeNode, sum: int) -> int:# 遍历所有节点 找有几条
# write code here
self.mp = {0:1}
return self.dfs(root, sum, 0)
def dfs(self, root, sum, last):# 以当前节点为根往下找
if not root: return 0
res = 0
temp = last + root.val
if temp-sum in self.mp.keys():# 曾经遍历的数据在里边 如果减掉某个值可以满足条件 那么就可以res+
# 换了一种写法在调整不从头开始
res += self.mp[temp - sum]
if temp not in self.mp.keys():# 存储数据
self.mp[temp] = 0
self.mp[temp] += 1
res = res +self.dfs(root.left, sum, temp)+self.dfs(root.right, sum, temp)# 找左右子节点
return res
10、二叉搜索树与双向链表
方法不一定是一样的,这个是视频讲的方法
class Solution:
def Convert(self , pRootOfTree ):
# write code here
# 能创建任何新的结点,只能调整树中结点指针的指向。
# 当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继
# 不懂什么是前驱后继
# 但是按照左中右就可以找到一个从大到小的链表了 当然 需要递归
if pRootOfTree==None:
return None
self.head=None
self.tail=None # 定义头尾 全局变量
def convert(cur):
if cur==None:
return
convert(cur.left)
if self.tail==None:# 还没有开始进行转换 这个就是头节点了
self.head=cur
else :# 将链表链接
self.tail.right=cur# 链表尾节点右指针指向现在的位置 # 当前节点的左指针指向尾节点
cur.left=self.tail
self.tail=cur
convert(cur.right)
convert(pRootOfTree)
# self.head.left,self.tail.right=self.tail,self.head# 不知道为什么 这个可以通过 有他反而会超时
# 因为要求是循环双向的 所以要头节点的左指向尾 尾节点的右指向头
return self.head
11、对称的二叉树
class Solution:#递归
def isSymmetrical(self , pRoot: TreeNode) -> bool:
# write code here
def isMirror(A,B):# 判断AB是否为镜像
#判断根节点是否相同 左子树和右子树是否是镜像的
if not A and not B:
return True
if not A or not B:
return False
if A.val!=B.val:
return False
return isMirror(A.left,B.right) and isMirror(A.right,B.left)
return isMirror(pRoot.left,pRoot.right) if pRoot else True
12、 合并二叉树(节点值相加或者把新节点放上去)
class Solution:
def mergeTrees(self , t1: TreeNode, t2: TreeNode) -> TreeNode:
# write code here
if not t1 :
return t2
if not t2:
return t1
t1.val += t2.val
t1.left = self.mergeTrees(t1.left, t2.left )
t1.right = self.mergeTrees(t1.right, t2.right)
return t1
13、二叉树的镜像
class Solution:
def Mirror(self , pRoot: TreeNode) -> TreeNode:
# write code here
# 递归 先交换左右子树 然后再分别对左右子树求镜像
if pRoot==None:
return None
pRoot.left,pRoot.right=pRoot.right,pRoot.left# 平行赋值
self.Mirror(pRoot.left)
self.Mirror(pRoot.right)
return pRoot
14、判断是不是二叉搜索树
class Solution:
def isValidBST(self , root: TreeNode) -> bool:
# write code here
stack = []
pre = None
cur = root
while cur or stack:# root的指针 (root剩下的) 和暂存root的stack 有一个不为空就继续进行
if cur:# cur不空
stack.append(cur)
cur = cur.left
else:# cur空
cur = stack.pop()
if pre and pre.val >= cur.val:
return False
pre = cur
cur = cur.right
return True
15、判断是不是完全二叉树
class Solution:
def isCompleteTree(self , root: TreeNode) -> bool:
# write code here
if not root:
return True
queue = [root]
flag = False
while queue:
n = len(queue)
for _ in range(n):
node = queue.pop(0)
if node is None:
flag = True
else:
#如果该节点不为空,直接将其左右孩子入队,
#这里不判断左右孩子是否为空,为空就入一个None,不为空就入本来的值
queue.append(node.left)
queue.append(node.right)
if flag == True and node != None :
#flag=True时,说明该节点为None,此时走到一下个节点,
#如果有一个不为空,则返回flase
return False
return True
16、判断是不是平衡二叉树
class Solution:
def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
# write code here
# 讲道理 是每一个根都得判断一下的 有不行的 就return false
if not pRoot:
return True
tmp=abs(self.blance(pRoot.left)-self.blance(pRoot.right))
return tmp<=1 and self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
# 左边右边都得查
def blance(self,pRoot):
if not pRoot:
return 0
return max(self.blance(pRoot.left),self.blance(pRoot.right))+1
17、二叉搜索树的最近公共祖先(给节点上的值找祖先)
class Solution:
def lowestCommonAncestor(self , root: TreeNode, p: int, q: int) -> int:
# write code here
while root:# 一层一层往下找 要么就是在一边 要么就是在两边 两边就是根 一边的话 就继续找
if root.val > p and root.val >q:
root = root.left
elif root.val < p and root.val < q:
root = root.right
else:
break
return root.val
18、在二叉树中找到两个节点的最近公共祖先(给节点上的值找祖先)(不是二叉搜索树了)
class Solution:
def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
# write code here
def dfs(root, o1, o2):
if not root:
return None
if root.val ==o1 or root.val==o2:
return root
left = dfs(root.left, o1, o2)
right = dfs(root.right, o1, o2)
if not left:
return right
if not right:
return left
return root
return dfs(root, o1, o2).val
19、序列化二叉树
class Solution:# 愿意按照什么顺序就按照什么顺序 只要自己能再反序列回来就行
def Serialize(self, root):# 序列化
# write code here
vals=[]
def encode(cur):# 把当前节点放进来 定义递归函数来处理
if not cur:
vals.append('#')
else:
vals.append(str(cur.val))
encode(cur.left)
encode(cur.right)
encode(root)
return ' '.join(vals)
def Deserialize(self, s):# 反序列化
# write code here
vals=iter(s.split())# iter是一个迭代器 可以迭代多次 直到不能迭代
def decode():
val=next(vals)
if val=='#':
return None
else:
cur=TreeNode(int(val))
cur.left=decode()
cur.right=decode()
return cur
return decode()
20、重建二叉树
class Solution:
def reConstructBinaryTree(self , pre: List[int], vin: List[int]) -> TreeNode:
# write code here
if not pre:
return None
if pre[0] == vin[0]:# 这个是只有一个根节点 没得左节点 所以直接写下去就行
ans = TreeNode(pre[0])
ans.right = self.reConstructBinaryTree(pre[1:], vin[1:])
return ans
else:
for i in range(len(vin)):
if pre[0] == vin[i]:# 找中序中的根节点
ans = TreeNode(pre[0])# ans就是root
ans.left=self.reConstructBinaryTree(pre[1:1+i], vin[:i])# 这个地方在递归调用函数
ans.right=self.reConstructBinaryTree(pre[1+i:], vin[i+1:])# 这个地方在递归调用函数
return ans
21、输出二叉树的右视图
class Solution:
def solve(self , xianxu: List[int], zhongxu: List[int]) -> List[int]:
# write code here
def buildtree(xianxu,zhongxu):
if not xianxu or not zhongxu:
return None
root = TreeNode(xianxu.pop(0))
idx = zhongxu.index(root.val)
root.left = buildtree(xianxu,zhongxu[:idx])
root.right = buildtree(xianxu,zhongxu[idx+1:])
return root
root = buildtree(xianxu,zhongxu)
stack = [root]
flag = 1
res = [root.val]
while stack:
cur = stack.pop(0)
flag -= 1
if cur.left:
stack.append(cur.left)
if cur.right:
stack.append(cur.right)
if flag == 0:
if stack:
res.append(stack[-1].val)
flag = len(stack)
return res
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)