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

https://www.1point3acres.com/bbs/thread-542250-1-1.html是这个帖子的后续。因为补充只能有200个字太烦了所以新发一帖。

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







                                                                       





补充内容 (2019-8-13 08:53):
postorder traversal忘记写return res[::-1]啦？补充一下。。https://leetcode.com/problems/binary-tree-postorder-traversal/

provhomme 发表于 2019-8-12 02:44
我感觉你的recommended post order不太对啊

你是说没有写return res[::-1]咩？忘记写了。。。https://leetcode.com/problems/binary-tree-postorder-traversal/

我感觉你的recommended post order不太对啊

楼主，post-order traversal 没必要keep track of all visited node吧，一个prev就足够了，这是我常用的写法
def postorder_traversal(root)
    return [] unless root
   
    rst, stack, curr, prev = [], [], root, nil
   
    while stack.any? || curr
        while curr
            stack << curr
            curr = curr.left
        end
        
        top = stack[-1]
        if top.right && prev != top.right
            curr = top.right
        else
            stack.pop()
            rst.push << top.val
            prev = top
        end
    end
    rst
end

顶一下lz

树只是一种特殊的图， 图学明白就好

visiting order并不重要，基本上pre order和in order就够了

linqiuli 发表于 2019-8-12 03:41
你是说没有写return res[::-1]咩？忘记写了。。。https://leetcode.com/problems/binary-tree-postorder- ...

我觉得这样并没有按照post order来traverse一个树，虽然这样倒序输出list是正确的答案。但如果面试官要求print出节点就不行了。

provhomme 发表于 2019-8-11 13:44
我感觉你的recommended post order不太对啊

少写了一步 return 的时候把结果反过来

torez 发表于 2019-8-12 08:36
楼主，post-order traversal 没必要keep track of all visited node吧，一个prev就足够了，这是我常用的写 ...

你这个不错诶。点赞！

provhomme 发表于 2019-8-12 04:55
我觉得这样并没有按照post order来traverse一个树，虽然这样倒序输出list是正确的答案。但如果面试官要求 ...

嗯，还是要看面试官的要求