樹的遍歷(Tree Traverse)

根節(jié)點(diǎn)=D=Degree 左節(jié)點(diǎn)=L=Left 右節(jié)點(diǎn)=R=Right

樹遍歷：

1.前序遍歷（DLR）
2.中序遍歷(LDR)
3.后序遍歷(LRD)
4.層次遍歷(一層一層的遍歷)
前三種遍歷均可用遞歸或者非遞歸的方式來遍歷。
層次遍歷可以設(shè)一個(gè)隊(duì)列蘸鲸，把元素放在隊(duì)列里耘斩，每次輸出隊(duì)頭元素顺少。

圖遍歷：

1.廣度優(yōu)先遍歷 也稱為廣度優(yōu)先搜索（BFS）（類似于樹的層次遍歷）
2.深度優(yōu)先遍歷 也稱為深度優(yōu)先搜索（DFS） （類似于樹的前序遍歷）
這兩種遍歷均可用來判斷圖的連通性。

深度優(yōu)先搜索(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())

廣度優(yōu)先搜索(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