Leetcode 100 같은 두 갈래 나무 110 균형 두 갈래 나무

오늘 가끔 leetcode를 뒤집어서 영어 사이트의 것도 시험해 봤는데 영어가 좋은 것 같아요. 토론 구역이 있고 답이 있고 비교가 되고 더 풍부해요.
100. 같은 나무
두 개의 두 갈래 나무를 정해서 함수를 만들어서 그것들이 같은지 확인하세요.
만약 두 나무가 구조적으로 같고 노드가 같은 값을 가지고 있다면 그것들은 같다고 여긴다.
예 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

사고방식은 차례차례 정상에서 아래로 찾는 과정이다.판단 두 가지 모두 공이면 True, 공이면 다른 공이면 False, 다음에val값이 같지 않으면 False, 그리고 좌우 나무가 맞지 않으면 False, 이런 것들은 더 이상 좌우 나무를 비교하지 않는다. 왼쪽 나무나 오른쪽 나무는 False가 직접 False로 돌아가는 것이다.코드는 다음과 같습니다.

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

class Solution:
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if p == None and q == None:
            return True
        elif (p == None and q != None) or (p != None and q == None):
            return False

        if p.val != q.val:
            return False
        elif (p.left != None and q.left == None) or (p.left == None and q.left != None) or \
            (p.right != None and q.right == None) or (p.right == None and q.right != None):
            return False
        else:
            result1 = self.isSameTree(p.left, q.left)
            if not result1:
                return False
            result2 = self.isSameTree(p.right, q.right)
            if not result2:
                return False

        return True

마지막에 좌우 트리를 판단했는데 처음에는 안 넣었어요. leetcode가 통과를 했지만 5% 정도의 코드만 이겼어요. 제가 과감하게 이 부분을 추가해서 미리 판단했는데 96.05%로 올라갔어요.시간의 복잡도 차이가 여전히 매우 크다는 것을 알 수 있다.
110. 평형 두 갈래 나무
두 갈래 나무를 정해 고도의 균형을 이루는 두 갈래 나무인지 아닌지를 판단한다.
이 문제에서 고도 균형 두 갈래 나무는 다음과 같이 정의된다.
두 갈래 나무의 각 노드의 좌우 두 개의 키 나무의 높이 차이의 절대치는 1을 넘지 않는다.
예 1:
주어진 두 갈래 나무[3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

복귀true.예 2:
주어진 두 갈래 나무[1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

복귀false.
사고방식은 바로 돌아가서 구자나무의 높이를 구하는 것이다.잎 노드의 아래는 바로 nil(알고리즘 도론 속의 그런 노드, 사실은 없다. 바로 None)의 높이가 0이다.각 노드(잎 노드 포함)의 높이는 두 개의 하위 노드 높이 중 큰 값인 +1입니다.그래서 calHeight 방법을 정의하는 것은 어렵지 않다.
이 문제의 관건은 어느 지점에서 높이차가 2보다 크면 FALSE로 제때에 돌아가야 한다는 것이다. 뒤에 있는 검사는 할 필요가 없다.나의 방법은 두 원소의list를 되돌려주는 것이다. 첫 번째는 높이이고, 두 번째는 검사가 필요한가 하는 것이다. 즉, 이전에 높이차가 1보다 작은지 아닌지를 판단한 것이다.마지막 코드는 다음과 같습니다.

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

class Solution:
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        result = self.calHeight(root, True)
        return result[1]

    def calHeight(self, node, needCheck):
        if not needCheck:
            return [2, False]
        else:
            if node == None:
                return [0, True]
            else:
                leftheight = self.calHeight(node.left, True)
                print(leftheight)
                if not leftheight[1]:
                    return [2, False]

                rightheight = self.calHeight(node.right, True)
                print(rightheight)
                if not rightheight[1]:
                    return [2, False]
                
                if abs(leftheight[0] - rightheight[0]) > 1:
                    return [2, False]
                else:
                    return [max(leftheight[0], rightheight[0]) + 1, True]

결국 비트는 100%python 코드를 사용했습니다. 하하하 반갑습니다!