アルゴリズム(14)-leetcode-explore-learn-データ構造-ツリーの遍歴

leetcode-explore-learn-データ構造-ツリー1

1.ツリーの深さ優先

1.1前順遍歴:中左右

1.2シーケンス遍歴:左中右

1.3後序遍歴:左右中

2.二叉木の広さは

を優先的に遍歴する
このシリーズのブログはleetcode-explore-learnサブ欄の学習ノートです.不明な点があれば、leetcode公式サイトを参照してください.https://leetcode-cn.com/explore/learn/card/data-structure-binary-tree/2/traverse-a-tree/7/
すべての例題のプログラミング言語はpythonツリーノード構造です.

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

1.ツリーの深さ優先ループ
ツリーの深さを優先する3つの遍歴方法:このシーケンスはルートノードがいつ遍歴するかです.
1.1前順遍歴:中程度
再帰的なフレームワークは、resリストに答えを追加し、内層に関数を定義する方法があります.

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res=[]
        def dfs_pre(node):
            if node==None:
                return
            res.append(node.val)
            dfs_pre(node.left)
            dfs_pre(node.right)
        dfs_pre(root)
        return res

反復フレーム:現在のノードの右サブツリーをスタックに入れて保存します.現在のノードの値をresに挿入し、現在のノードを現在のノードの左サブツリーノードに更新します.

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        stack=[]
        res=[]
        node=root
        while(node or stack):
            if node:
                res.append(node.val)
                if node.right:
                    stack.append(node.right)
                node=node.left
            else:
                node=stack.pop()
        return res

1.2.シーケンシャルパス:左中右
再帰的なフレームワークは、シーケンスループと同じです.

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res=[]
        def dfs_inorder(node):
            if node==None:
                return
            dfs_inorder(node.left)
            res.append(node.val)
            dfs_inorder(node.right)
        dfs_inorder(root)
        return res

反復フレームワーク:stackに何を置く必要がありますか.ルートノードは左に最後まで行きます.ルートノードをすべて入れて、入れたのはあるノードです.最後まで回った後、一つ一つ弾き出す.そしてそのノードの右サブツリーに行き、右サブツリーが空の場合、そのノードの親ノードを弾きます.右サブツリーが空でない場合は、右サブツリーの処理を反復できます.

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        stack=[]
        res=[]
        node=root
        while(stack or node):
            if node:
                stack.append(node)
                node=node.left
            else:
                node=stack.pop()
                res.append(node.val)
                node=node.right
        return res

1.3後序遍歴:左右中
再帰的なフレームワークとシーケンス、中シーケンスの遍歴が一致

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res=[]
        def dfs_post(node):
            if node==None:
                return
            dfs_post(node.left)
            dfs_post(node.right)
            res.append(node.val)
        dfs_post(root)
        return res

反復のフレームワーク:中右左の逆順は、左右中です.擬似プリアンブルループ(左ノードを保存)の結果、逆シーケンスで出力します.

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        stack=[]
        res=[]
        node=root
        while(stack or node):
            if node:
                res.append(node.val)
                if node.left:
                    stack.append(node.left)
                node=node.right
            else:
                node=stack.pop()
        return res[::-1]

2.二叉木の広さ優先遍歴
-階層遍歴、キューによる広さ優先遍歴の実現を支援
再帰フレームワーク:ノードが置かれている階層を格納するためにlevel情報が必要です.問題:resの階層はどこに追加されますか–ソリューションは、まずl階層が存在するかどうかを判断し、いなければ追加されます.

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root==None:
            return []
        res=[]
        def bfs(node,l):
            if node==None:
                return
            if l>len(res)-1:
                res.append([])
            res[l].append(node.val)
            bfs(node.left,l+1)
            bfs(node.right,l+1)
        bfs(root,0)
        return res
        

反復フレームワーク:キュー、先頭先頭先頭先頭、レイヤごとにキューの長さを統計し、ポップアップする要素の数を確認します.

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root==None:
            return []
        que=[root]
        res=[]
        l=0
        while(que):
            n=len(que)
            res.append([])
            for i in range(n):
                node=que.pop(0)
                res[l].append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
            l+=1
        return res