重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
前序遍历 [根｜左｜右]
中序遍历 [左｜根｜右]
- 前序遍历的第一个节点是root
- 根据这个root在终须遍历里面去找，left side 是左子树，right side是右子树
- 根据上述的左右子树点的数量，再去划分前序遍历，找到前序的左子树、右子树
分治
- 递归参数为三个idnex，分别为当前root所在的前序遍历的index（用于定位root），对应子树在中序遍历list的最左、最右index（用于定位整个子树是哪一串）
- stopcase：left > right，越界，返回null
- 分别在前序、中序中划分左右子树
- 递归重建左右子树
image.png
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
def recur(i,l,r):
if l > r: return
node = TreeNode(preorder[i]) # 用idnex从前序遍历中找到root val，并且构建
i2 = inorder.index(preorder[i]) # 找到当前root在中序的index
# left_side: inorder[l:root_i - 1] ->利用这个确定左子树
# -> 一共有root_i-1 - l个元素 -> 该长度用于确认前序的右子树根节点index
# right_side: inorder[root_i+1,r] -> 利用这个确定右子树
# [root] [ left side ] [ right side ]
# i i+1 i+1+len+1
# left root right root
# [ left side ][root][ right side ]
# l i2 r
# len = i2-l
node.left = recur(i+1, l,i2-1) # 当前root index下一位 即为左子树开始
node.right = recur(i+1+i2-l,i2+1,r)
# root [root+1 ........ root+1+(root_i-l-1) ] [right children]
# len(left_side) = root_i-l-1 |-> root+1+(root_i-l-1) + 1
return node
return recur(0,0,len(inorder)-1)
判断是否为二叉搜索树的后序遍历
后续遍历 [左｜右｜根]
- 通过递归，判断所有子树的正确性
- stop case：l >= r (叶子结点)
- 递归：划分左右子树（由于是二叉搜索树，左<根<右）；分别判断左右子树是否为后序
-
判断依据：左子树都小于root，右子树都大于root
image.png
由于left全部都小于root，right都大于root
list[i+1]就是第一个大于root的
class Solution:
def verifyPostorder(self, postorder: List[int]) -> bool:
def recur(l,r):
# stop case
if l >= r: return True
# [ left ][ right ][root]
# l i-1 i r-1 r
# 划分左右子树
root = postorder[r]
for i in range(l,r+1):
# 找到第一个大于root的元素，即为右子树开始的地方
# 同时也判断了左子树是否符合要求
if postorder[i] > root:
break
# left_side = postorder[l,i]
# right_side = postorder[i,r]
# 判断右子树是否都大于root (存在flage中，也就是当前这个node判断是否为后序）
flage = False if postorder[i:r] and min(postorder[i:r]) < root else True
return flage and recur(l,i-1) and recur(i,r-1)
return recur(0,len(postorder)-1)
数值的整数次方
- 通过当前的指数n进行简化
- 如果n是奇数 x^(2n+1) = xx^nx^n
- 如果n是偶数 x^(2n) = xn*xn
- 如果遇到奇数，把这个单独的x先乘到res里面存着
- 剩下的利用 x -> x^2， n->n/2进行底数的更新，减少迭代次数
class Solution:
def myPow(self, x: float, n: int) -> float:
# 数学简化 x^-n = (1/x)^n
if n < 0:
x, n = 1/x, -n
# x^2n = (x^n) * (x^n)
# x^(2n+1)= x * (x^n) * (x^n)
res = 1
while n:
if n%2 == 1:
res *= x # 把单独的那个先乘到res里
x *= x
n = n//2 # 直接用降一个二次幂
return res
