leetcode-二叉木の前序、中序、後序、層序の再帰と非再帰実現

文書ディレクトリ

1. 二叉木の遍歴

2. フロントシーケンス

2.1. 再帰実装

2.2. 非再帰実装

3. 中順遍歴

3.1. 再帰実装

3.2. 非再帰実装

4. ポストシーケンス

4.1. 再帰実装

4.2. 非再帰実装

5. 層順遍歴

1.ツリーの遍歴
面接の中で、特に校招面接の中で(ははは、社招面接の推定はこのようなテーマがあまりにも簡単で、考察を潔しとしないことを嫌っている)、よく聞かれるテーマの一つは二叉樹の各種遍歴アルゴリズムで、私たちがよく見られる二叉樹の遍歴方式は前序遍歴、中序遍歴、後序遍歴、層序遍歴があります.前順/中順/後順とはルートノードを巡回する順序であり、層順巡回はツリーの深さ方向に沿って巡回し、対応する巡回ノードの順序は以下の通りである.

前シーケンスループ:ノードを最初にループします.ルートノード->左サブツリー->右サブツリーの順にループします.

のシーケンシャルループ:ルートノードを中間ループします.巡回順は左サブツリー->ルートノード->右サブツリーです.

後順ループ:ルートノードを最後にループします.巡回順は左サブツリー->右サブツリー->ルートノードです.

層序遍歴:二叉木の第1層のルートノードから遍歴し、第2層は最も左から右へ遍歴し、第3層は最も左から右へ遍歴する.の

2.前段遍歴
タイトルリンク:https://leetcode.com/problems/binary-tree-preorder-traversal
2.1. 再帰的な実装
次のコードのresは、グローバル変数です.

def binary_tree_pre_order_traversal(root, res):
    if root:
        res.append(root.val)
        binary_tree_pre_order_traversal1(root.left, res)
        binary_tree_pre_order_traversal1(root.right, res)

2.2. 非再帰的実装
スタックを使用してツリー内のノードを保存し、スタックを列データ構造で実装します.

def binary_tree_pre_order_traversal(root):
    res = []
    s = []
    if root:
        s.append(root)
    while s:
        root = s.pop()
        res.append(root.val)
        if root.right:
            s.append(root.right)
        if root.left:
            s.append(root.left)

    return res

3.中順遍歴
タイトルリンク:https://leetcode.com/problems/binary-tree-inorder-traversal
3.1. 再帰的な実装
次のコードのresは、グローバル変数です.

def tree_in_order_traversal(root, res):
    if root:
        tree_in_order_traversal1(root.left, res)
        res.append(root.val)
        tree_in_order_traversal1(root.right, res)

3.2. 非再帰的実装

def tree_in_order_traversal(root):
    res = []
    s = []
    while root or s:
        while root:
            s.append(root)
            root = root.left
        root = s.pop()
        res.append(root.val)
        root = root.right
    return res

4.後段遍歴
4.1. 再帰的な実装
次のコードのresは、グローバル変数です.

def binary_tree_post_order_traversal1(root, res):
    if root:
        binary_tree_post_order_traversal1(root.left, res)
        binary_tree_post_order_traversal1(root.right, res)
        res.append(root.val)

4.2. 非再帰的実装
二叉木の後続遍歴の非再帰的実現方式が前序遍歴、中序遍歴よりも難易度が高いのは(ハハ、私が言ったのではなくleetcodeが言ったのですが、leetcodeが後序遍歴に与えた難易度tagはhardで、前序遍歴、中序遍歴の難易度tagはmediumです)、後序遍歴が最後であるためルートノードを遍歴し、私たちの通常の方法は上から下へ遍歴するので、必ずルートノードを通ります.だから、ルートノードを保存しなければなりません.左ノードを先に遍歴しなければなりません.だから、保存しなければなりません.そのため、ステップは前の遍歴と中の遍歴よりも多くなります.具体的な世代コードは以下の通りです.

def binary_tree_post_order_traversal2(root):
    res = []
    s =[]
    while root or s:
        while root:
            s.append(root)
            if root.left:
                root = root.left
            else:
                root = root.right
        root = s.pop()
        res.append(root.val)
        if len(s) > 0 and s[-1].left == root:
            root = s[-1].right
        else:
            root = None
    return res

5.層順遍歴
タイトルリンク:https://leetcode.com/problems/binary-tree-level-order-traversal

def binary_tree_level_order_traversal(root):
    if not root:
        return []
    res = [[root.val]]
    d = deque([root])

    while d:
        tmp_val = []
        for _ in range(0, len(d)):
            tmp_node = d.popleft()
            if tmp_node.left:
                d.append(tmp_node.left)
                tmp_val.append(tmp_node.left.val)
            if tmp_node.right:
                d.append(tmp_node.right)
                tmp_val.append(tmp_node.right.val)
        if tmp_val:
            res.append(tmp_val)

    return res