知前序中序重建二叉树
class TreeNode():
def __init__(self,num):
self.val=num
self.left=None
self.right=None
def reconstructbinarytree(pre,tin):#pre:前序list tin:后序list
if not pre or not tin:
return None
root=TreeNode(pre.pop(0))
idx=tin.index(root.val)
root.left=reconstructbinarytree(pre,tin[:idx])
root.right=reconstructbinarytree(pre,tin[idx+1:])
return root
二叉树镜像
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回镜像树的根节点
def Mirror(self,root):
# write code here
if root:
root.right,root.left=self.Mirror(root.left),self.Mirror(root.right)
return root
else:
return None
二叉树深度
class Solution:
def TreeDepth(self, pRoot):
# write code here
if not pRoot:
return 0
l=self.TreeDepth(pRoot.left)
r=self.TreeDepth(pRoot.right)
return(l+1) if l>r else (r+1)
判断是否是平衡二叉树
class Solution:
def deepth(self, root):
if not root:
return 0
left=self.deepth(root.left)
right=self.deepth(root.right)
return max(left+1,right+1)
def IsBalanced_Solution(self, pRoot):
if not pRoot:
return True
l=self.deepth(pRoot.left)
r=self.deepth(pRoot.right)
if abs(l-r)<2 and self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.left):
return True
else:
return False
是否是二叉树
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
def helper(node, lower = float('-inf'), upper = float('inf')) -> bool:
if not node:
return True
val = node.val
if val <= lower or val >= upper:
return False
if not helper(node.right, val, upper):
return False
if not helper(node.left, lower, val):
return False
return True
return helper(root)
class Solution:
pre=-inf
def isValidBST(self, root: TreeNode) -> bool:
if root==None:
return True
if not self.isValidBST(root.left):
return False
if root.val<=self.pre:
return False
self.pre=root.val
return self.isValidBST(root.right)
二叉树删除
class Solution:
def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
if not root:
return None
# 就是说找到节点之后 在把左右子树放到正确的位置上去
if root.val > key:
root.left = self.deleteNode(root.left, key)
return root
elif root.val < key:
root.right = self.deleteNode(root.right, key)
return root
else:
# 就是找到当前节点了 看他的左子树 还是右子树
left = root.left
right = root.right
if not left:
# 左子树为空
return root.right
elif not right:
# 右子树为空
return root.left
else:
# 左右子树都不为空 可以找到右子树的最左节点
# 这是用来给上一级返回的
r = right
while right.left:
right = right.left
right.left = left
return r
作者：zhangenqi
链接：https://leetcode-cn.com/problems/delete-node-in-a-bst/solution/si-lu-bu-nan-shi-you-fan-hui-zhi-de-by-zhangenqi/
