树

树的遍历(Tree Traverse)

深度优先搜索(DFS)

递归(Recurision)

def re(self.root):
    if not root:
        return None
    #插入部分, preorder, inorder, postorder

前序遍历(preorder)

    print(root.val)
    self.re(root.left)
    self.re(root.right)

中序遍历(inorder)

    self.re(root.left)
    print(root.val)
    self(root.right)

后序遍历(postorder)

    self.re(root.left)
    self.re(root.right)
    print(root.val)

利用递归找寻最大深度

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        left_max = self.maxDepth(root.left)
        right_max = self.maxDepth(root.right)
        return max(left_max, right_max)+1

非递归（Non-recurision)

前序遍历(preorder)
方法一

stack,node=[],root
while stack or node:
    while node:
        print(node.val)
        stack.append(node)
        node=node.left
    node=stack.pop()
    node=node.right

方法二

stack=[root]
while len(stack)>0:
    print(root.val)
    if root.right:
        stack.append(root.right)
    if root.left:
        stack.append(root.left)
    root=stack.pop()

中序遍历(inorder)

stack, node= [], root
while stack or node:
    while node:
        stack.append(node)
        node=node.left
    node=stack.pop()
    print(node.val)
    node=node.right

后序遍历(postorder)
方法一

stack1, stack2, node=[], [], root
while stack1 or node:
    while node:
        stack1.append(node)
        stack2.append(node)
        node=node.right
    node=stack1.pop()
    node=node.left
while stack2:
    print(stack2.pop().val())

方法二

stack, stack2=[root], []
while len(stack)>0:
     node=stack.pop()
     stack2.append(node)
     if node.left:
        stack.append(node.left)
     if node.right:
        stack.append(node.right)
while len(stack2)>0:
     print(stack2.pop().val())

广度优先搜索(BFS)

层次遍历(level traversal)

stack, node = [root], root
while stack:
    node = stack.pop(0)
    print (node.val)
    if node.left: 
       stack.append(node.left)
    if node.right: 
       stack.append(node.right)

利用BFS找寻树的最大深度

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        stack = [root]
        level = 0
        while stack:
            level = level+1
            for _ in range(len(stack)):
                root = stack.pop(0)
                if root.left:
                    stack.append(root.left)
                if root.right:
                    stack.append(root.right)
        return level