アルゴリズム(15)-leetcode-explore-learn-データ構造-再帰的に二叉木の問題を解決する

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

1.概要

2.トップダウン/ボトムアップフレームワーク思想

3.例題

3.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.概要
ツリー構造自体は再帰的に定義されます.値と他のノードを指すリストを含むノードです.ツリーの多くの問題は再帰的に解決できる.各再帰レベルでは、単一のノード内の問題に注目し、再帰コールによってサブノードの問題を解決する必要があります.
ツリーの問題は、通常、トップアップまたはボトムアップの再帰によって解決されます.
再帰解題は、再帰関数と元の関数が存在する必要があり、元の関数では再帰入口が開き、再帰関数は絶えず再帰的に解く.
2.トップダウン/ボトムアップフレームワーク思想
トップアップ/ボトムアップ-ツリーの最大深さを理解するための質問です
上から下へ:各再帰レベルで、ノードにアクセスして値を計算し、再帰呼び出し時にサブノードに渡します.上から下へのスキームは,先行ループと見なすことができる.
ルートノードの深さは1であり、1つのノードの深さがxである場合、サブノードの深さがわかります.再帰呼び出し時にノードの深さを上から下へパラメータに渡すと、各ノードは自分の深さを知っています.リーフノードでは、より大きな深さを更新する必要があるかどうかを比較することで決定できます.

class Solution(object):
    def __init__(self):
        self.res=0
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def dfs_top_down(node,l):
            if node==None:     # root          
                return
            if node.left==None and node.right==None:
                self.res=max(self.res,l)          #  max             
            dfs_top_down(node.left,l+1)
            dfs_top_down(node.right,l+1)
        dfs_top_down(root,1)
        return self.res

下から上へ:各再帰レベルで、すべてのノードに対して関数を再帰的に呼び出し、戻り値とルートノード自体の価値に基づいて答えます.下から上へのスキームは後順遍歴と見なすことができる
ルートノードが左サブノードをルートとする最大深さl、右サブノードをルートとする最大深さが分かる場合、このルートノードが存在するサブツリーの最大深さはm a x(l,r)+1 max(l,r)+1 max(l,r)+1(各ノードの答えは、サブノードの問題を解決した後に答えを得ることができる)である.

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def dfs_bottom_up(node):
            if node==None:
                return 0
            left_l=dfs_bottom_up(node.left)
            right_l=dfs_bottom_up(node.right)
            return max(left_l,right_l)+1
        res=dfs_bottom_up(root)
        return res 

ツリー再帰フレームワークの考え方:トップダウン:いくつかのパラメータとノード自体の値を使用してサブノードに渡すパラメータをボトムアップから決定する必要があります:サブノードの答えを知っていれば、そのノードの答えを知ることができ、ボトムアップを採用するのは良い選択です
3.例題
3.1対称二叉木
二叉木を与え、ミラー対称思考に失敗したかどうかを確認します.ノートは編集状態を参照してください.
コアはrootサブツリーとrootサブツリーが鏡面対称であるかどうかを検証することです.もしそうなら、単独のrootツリーは鏡面対称です.公式の解の構想は再帰的に参考にします:もし1つの木の左の子の木と右の子の木が鏡像対称であれば、この木も対称です.問題は、2つのサブツリーがどのような場合に対称になるかということです.ノードと同じ値2を持つ.各ツリーの右サブツリーは、別の数の左サブツリーと対称です.

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def ismirror_bottom_up(node1,node2):
            if node1==None and node2==None:
                return True
            if node1==None or node2==None:
                return False
            return node1.val==node2.val and ismirror_bottom_up(node1.left,node2.right) and ismirror_bottom_up(node1.right,node2.left)
        flag=ismirror_bottom_up(root,root) # root  root   ，root       
        return flag

反復の解法:キューは[root,root]に初期化され、比較する必要がある点を隣接する位置に配置します.2つのノードが同時にポップアップされるたびにnode 1.leftとnode 2.rightはキューに入れます.node 1.rightとnode 2.leftはキューに入れます.このようにして、対比が完了するまでポップアップされるノードが押し込まれる.

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        que=[root,root]
        while(que):
            node1=que.pop(0)
            node2=que.pop(0)
            if node1==None and node2==None:
                continue
            if node1==None or node2==None:
                return False
            if node1.val!=node2.val:
                return False
            que.append(node1.left)
            que.append(node2.right)
            que.append(node1.right)
            que.append(node2.left)
        return True

3.2パス合計
ツリーとターゲット和を指定し、ツリーにルートノードからリーフノードへのパスが存在するかどうかを判断します.このパスのすべてのノード値がターゲット和に加算されます.
直感的に上から下まで、実行可能な考え方です.各ノードでターゲット値-ノード値を次のノードに渡し、繰り返します.リーフノードで0に減算すると、パス上のすべてのノードの値がターゲットと等しく加算されるパスが存在することを示します.再帰関数は、TrueまたはFalseプログラム実装上のすべてのパスを巡回し、すべての結果を取得することができますが、Trueとして実際に再帰すると終了することができます.これはどのように書きますか.

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        def has_top_down(node,target):
            if node==None:
                return False
            if node.left==None and node.right==None:
                if target-node.val==0:
                    return True
            if has_top_down(node.left,target-node.val):
                return True
            if has_top_down(node.right,target-node.val):
                return True
            return False
        return has_top_down(root,sum)

各ノードと一致する情報を格納するスタックを維持します.スタックからノードがポップアップされるたびに、そのノードがリーフノードであるか否かを判断し、リーフノードである場合、対応するターゲット値-ノード値が0であるか否かを判断する.ノードがリーフノードでない場合は、サブノードと対応する情報をスタックに押し込みます.–スタックは、深度優先ループの構造を維持し、1つのパスをループした後、他のパスをループします.最初のパスは一番右のパスで、右から左にスキャンするプロセスです.

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if root==None:
            return False
        stack=[(root,sum)]
        while(stack):
            node,target=stack.pop()
            if node.left==None and node.right==None and node.val-target==0:
                return True
            if node.left:
                stack.append((node.left,target-node.val))
            if node.right:
                stack.append((node.right,target-node.val))
        return False