分享一下自己写binary tree的感悟

总结了一下发现其实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有得天独厚的优势,所以看见了就想想我们需要一个全局变量。但是,全局变量就像中央空调,(鄙视),一般能不用就不用,其他的题都可以用常规的递归解决。
今天又是开心的刷题的一天尼~