二叉樹先序、中序、後序周遊 遞歸與非遞歸 Python實作

1.先序周遊：根節點->左子樹->右子樹 

先序列印二叉樹（遞歸）

def preOrderTraverse(node):
    if node is None:
        return None
    print(node.val)
    preOrderTraverse(node.left)
    preOrderTraverse(node.right)
           

 先序列印二叉樹（非遞歸）

def preOrderTravese(node):
    stack = [node]
    while len(stack) > 0:
        print(node.val)
        if node.right is not None:
            stack.append(node.right)
        if node.left is not None:
            stack.append(node.left)
        node = stack.pop()
           

2.中序周遊：左子樹->根節點->右子樹

 中序列印二叉樹（遞歸）

def inOrderTraverse(node):
    if node is None:
        return None
    inOrderTraverse(node.left)
    print(node.val)
    inOrderTraverse(node.right)
           

中序列印二叉樹（非遞歸）

def inOrderTraverse(node):
    stack = []
    pos = node
    while pos is not None or len(stack) > 0:
        if pos is not None:
            stack.append(pos)
            pos = pos.left
        else:
            pos = stack.pop()
            print(pos.val)
            pos = pos.right
           

 Lecode上題目：

驗證二叉搜尋樹

給定一個二叉樹，判斷其是否是一個有效的二叉搜尋樹。

假設一個二叉搜尋樹具有如下特征：

• 節點的左子樹隻包含小于目前節點的數。
• 節點的右子樹隻包含大于目前節點的數。
• 所有左子樹和右子樹自身必須也是二叉搜尋樹。

樹的中序周遊實作：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        stack = []
        pos = root
        pre = cur = None
        while pos !=None or len(stack) > 0:
            if pos!= None:
                stack.append(pos)
                pos = pos.left
            else:
                pos = stack.pop()
                if pre == None:
                    pre = pos.val
                else:
                    cur = pos.val
                    
                    if cur <= pre:
                        return False
                    else:
                        pre = cur
                pos = pos.right
        
        return True
           

3.後序周遊：左子樹->右子樹->根節點

後序列印二叉樹（遞歸） 

def postOrderTraverse(node):
    if node is None:
        return None
    postOrderTraverse(node.left)
    postOrderTraverse(node.right)
    print(node.val)
           

# 後序列印二叉樹（非遞歸）

# 使用兩個棧結構

# 第一個棧進棧順序：左節點->右節點->跟節點

# 第一個棧彈出順序： 跟節點->右節點->左節點(先序周遊棧彈出順序：跟->左->右)

# 第二個棧存儲為第一個棧的每個彈出依次進棧

# 最後第二個棧依次出棧

def postOrderTraverse(node):
    stack = [node]
    stack2 = []
    while len(stack) > 0:
        node = stack.pop()
        stack2.append(node)
        if node.left is not None:
            stack.append(node.left)
        if node.right is not None:
            stack.append(node.right)
    while len(stack2) > 0:
        print(stack2.pop().val)
           

 4.按層周遊：從上到下、從左到右按層周遊

先進先出選用隊列結構

import queue
def layerTraverse(head):
    if not head:
        return None
    que = queue.Queue()      # 建立先進先出隊列
    que.put(head)
    while not que.empty():
        head = que.get()    # 彈出第一個元素并列印
        print(head.val)
        if head.left:       # 若該節點存在左子節點,則加入隊列（先push左節點）
            que.put(head.left)
        if head.right:      # 若該節點存在右子節點,則加入隊列（再push右節點）
            que.put(head.right)
           

 5.二叉樹節點個數

def treeNodenums(node):
    if node is None:
        return 0
    nums = treeNodenums(node.left)
    nums += treeNodenums(node.right)
    return nums + 1
           

 6.二叉樹的最大深度

def bTreeDepth(node):
    if node is None:
        return 0
    ldepth = bTreeDepth(node.left)
    rdepth = bTreeDepth(node.right)
    return (max(ldepth, rdepth) + 1)