100-同じツリー-python

2つのツリーを指定し、同じかどうかを確認するために関数を作成します.2つのツリーが構造的に同じで、ノードが同じ値を持っている場合は、同じとみなされます.
例1:

  :       1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

  : true

例2:

  :      1          1
          /           \
         2             2

        [1,2],     [1,null,2]

  : false

例3:

  :       1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

  : false

2本の木は同じで木の中のすべてのノードが同じであることを満たし、すなわちnode.valnode.left・node.rightと同じであるべきである.ツリーの性質から,2つのツリーが同じであれば,それらの遍歴シーケンスも必然的に同じである.したがって、2つのツリーをそれぞれ巡回することによって、それらの巡回シーケンス(前の巡回、中の巡回、後の巡回のいずれか)を取得し、シーケンスが同じかどうかを判断することができます.

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p == None and q == None: return True
        if p == None or q == None: return False

        r1, r2 = [], []
        def inorder(root, index):
            if root == None:
                if index == 1: r1.append(-1)
                else: r2.append(-1)
                return None

            if index == 1: r1.append(root.val)
            else: r2.append(root.val)
            inorder(root.left, index)
            inorder(root.right, index)

        inorder(p, 1)
        inorder(q, 2)
        
        return r1 == r2 

中シーケンスパスを用いて従来から判断を補助してきたほか,反復法によりサブツリーが同じかどうかを直接再帰的に判断することもできる.

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p == None and q == None: return True
        if p == None or q == None: return False
			
		#               ，       
		if p.val != q.val:
			return False
		#                    
		return self.isSameTree(p.rihgt, q.right) and self.isSameTree(p.left, q.left)

第1の方法は追加の配列を用い,第2の方法は再帰的にスタックを導入するので,両者の空間的複雑度はO(N)O(N)O(N)O(N)である.判断プロセスはツリー内の各ノードにアクセスする必要があるため,時間的複雑度はO(N)O(N)O(N)である.