树的遍历(Tree Traverse)
根节点=D=Degree 左节点=L=Left 右节点=R=Right
树遍历：
1.前序遍历（DLR）
2.中序遍历(LDR)
3.后序遍历(LRD)
4.层次遍历(一层一层的遍历)
前三种遍历均可用递归或者非递归的方式来遍历。
层次遍历可以设一个队列，把元素放在队列里，每次输出队头元素。
图遍历：
1.广度优先遍历 也称为广度优先搜索（BFS）（类似于树的层次遍历）
2.深度优先遍历 也称为深度优先搜索（DFS） （类似于树的前序遍历）
这两种遍历均可用来判断图的连通性。
深度优先搜索(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
