总结了一下发现其实binary tree蛮常规的。就是有时候用全局pointer变来变去可以降低复杂度有点绕。分享一下也当作练习了。
首先必备的三种recursion方式,也可以看到pre,in,post都是针对于visit root的顺序来定义的。对于inorder,如果是BST的话, 得到的是ascending order的。这一点比较重要。在convert sorted result to bst can be very useful (leetcode 109)
def preorder(root): def inorder(root): def postorder(root):
visit(root.val) inorder(root.left) postorder(root.left)
preorder(root.left) visit(root.val) postorder(root.right)
preorder(root.right) inorder(root.right) visit(root.val)
然后iterative,都要用到stack. postorder最好利用inorder小改的方式写。不然我们要记录回溯到root的方式。(不能root,root.right root这种循环。所以要用一个数组记录visited root)
def preorder(root): def inorder(root): def postorder(root): *** recommend def postorder(root):
stack=[root] stack=[] visited,stack=set(),[] stack=[root]
while(stack): while(stack or root): while(stack or root): while(stack):
node=stack.pop() while(root): while(root): node=stack.pop()
visit(node) stack.append(root) stack.append(root) visit(node)
if node.right: root=root.left root=root.left if node.left:
stack.append(node.right) node=stack.pop() node=stack.pop() stack.append(node.left)
if node.left: visit(node) if node.right and not node.right in visited: if node.right:
stack.append(node.left) root=node.right stack.append(node) stack.append(node.right)
root=node.right
else:
visited.add(node)
visit(node)
root=None
leetcode 109, 简单的recursion要nlogn的复杂度。因为每次我们要找到中间点。换成array进行处理,虽然复杂度降下来了但是会有额外的空间复杂度。如果我们用global variable记录我们traverse的状态,再结合inorder 得到有序数组的性质,就是很优解啦。
n=def getsize(head):->get the size of the lincked list
def help(l,r):
if l>r:
return
mid=(l+r)/2
left=help(l,mid-1) 先记录往左边走的node
root=TreeNode(head.val) 左边走完了,现在我们在head点
head=head.next 要往下走了,拿着小本本再走一步
root.right=help(mid+1,r)
root.left=left
return root
这种写法,就是坚信left一定是我们处理完的点(相信自己~~),然后我们带着小本本一定站在了正确的点(head是我们处理好的点)最后我们带着小本本往下走。
再来看用这种方式写leetcode99.如果不用morris traversal,用pred记录上一个visit的点。
standard inorder iterative:
stack=[]
first,second,pred=None,None,None
while (stack or root):
while(root):
stack.append(root)
root=root.left
node=stack.pop()
if pre.val<node.val:
....
pre=node
root=node.right
现在看来,一般对于有序+bt,inorder有得天独厚的优势,所以看见了就想想我们需要一个全局变量。但是,全局变量就像中央空调,(鄙视),一般能不用就不用,其他的题都可以用常规的递归解决。
今天又是开心的刷题的一天尼~