程序recoverTree()运行的流程：
根节点先入栈
左子树自顶向下依次入栈，自底向上和子树右节点，子root节点对比，直至树根节点root
右子树自顶向下依次入栈, 自底向上和子树右节点，子root节点对比，直至树根节点root
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution(object):
def recoverTree(self, root):
stack = []
wrong1 = wrong2 = p = None
while stack or root:
while root:
stack.append(root) #第一压入根节点root入栈
root = root.left #压入所有左节点入栈
root = stack.pop() #取出栈顶的节点，然后传给p
if p and root.val < p.val: #第一次p是没有值的，不会执行
wrong2 = root
if wrong1 is None: # 没法同时赋值两个值，必须一个一个来
wrong1 = p
else:
break
p = root #把栈顶的值传给p
root = root.right #把右子树传給root，等到while root时，会把右子树全部入栈
wrong1.val, wrong2.val = wrong2.val, wrong1.val
def recoverTree2(self,root): #第二种解法，这个比较直观但速度比第一种慢，遍历了2次
rs = []
def bfs(root):
if not root:
return
bfs(root.left)
rs.append(root)
bfs(root.right)
bfs(root)
x,y=None,None
pre = rs[0]
for i in range(1,len(rs)):
if pre.val> rs[i].val:
y = rs[i]
if x == None:
x = pre
pre=rs[i]
if x and y:
x.val,y.val=y.val,x.val
def create_tree(nodes):
def helper(node, i): # 用列表递归创建二叉树，
if i < len(nodes): # 当下标索引满足条件时
if nodes[i] in ['#', None]: # 如果列表中下标为i的结点为空
return None # 返回None
else:
node = TreeNode(nodes[i]) # 构建当前结点
node.left = helper(node.left, 2 * i + 1) # 构建左子树，通过下标查找
node.right = helper(node.right, 2 * i + 2) # 构建右子树，通过下标查找
return node # 返回根节点为下标为i的元素的子树
return node # 返回根节点
root = TreeNode(0) # 临时结点
root = helper(root, 0) # 建立树
return root
if __name__ == '__main__':
lst = [1, 3, None, None, 2]
root = create_tree(lst)
a = Solution()
a.recoverTree(root)
网友评论