参考[LeetCode] questions conlusion_InOrder, PreOrder, PostOrder traversal 可以对binary tree进行遍历。

 

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

此处说明Divide and Conquer 的做法，其实跟recursive的做法很像，但是将结果存进array并且输出，最后conquer (这一步worst T：O(n)) 起来，所以时间复杂度可以从遍历O(n) -> O(n^2).

实际上代码是一样, 就是把[root.val] 放在先, 中, 后就是pre, in, post order了.

1) Preorder traversal

class Solution:
    def preOrder(self, root):
        if not root: return []
        left = self.preOrder(root.left)
        right = self.preOrder(root.right)
        return [root.val] + left + right  # worst T: O(n)

 

2) 

Inorder traversal

class Solution:
    def inOrder(self, root):
        if not root: return []
        left = self.preOrder(root.left)
        right = self.preOrder(root.right)
        return  left + [root.val] + right  # worst T: O(n)

 

3) Postorder traversal

class Solution:
    def postOrder(self, root):
        if not root: return []
        left = self.preOrder(root.left)
        right = self.preOrder(root.right)
        return  left + right + [root.val] # worst T: O(n)

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄