검지 Offer 17번 - 나무의 자 구조

1877 단어

제목


두 그루의 두 갈래 나무 A, B를 입력하여 B가 A의 자 구조인지 아닌지를 판단한다.(ps: 우리는 빈 나무가 임의의 나무의 하위 구조가 아니라고 약속한다)

생각


무엇이 두 갈래 나무의 자 구조와 자 나무입니까?
  • 자목은 하나의 결점을 포함하고 이 결점 아래의 모든 노드를 포함해야 한다는 뜻이다. 한 그루의 크기가 n인 두 갈래 나무는 n자목이 있는데 각각의 결점을 뿌리로 하는 자목이다
  • 자 구조는 하나의 결점을 포함하고 왼쪽 나무나 오른쪽 나무만 취할 수 있거나 모두 취하지 않을 수 있다는 뜻이다

  • 기본적인 사상은 우리가 먼저 A, B가 비어 있는지 아닌지를 판단하고 어느 것이 비어 있으면 바로 False로 돌아가는 것이다.그리고 A, B 두 노드의 값이 같은지 판단하고 같지 않으면 False로 바로 돌아갈 수 있습니다.만약 같다면 A의 왼쪽 나무와 B의 왼쪽 나무, A의 오른쪽 나무와 B의 오른쪽 나무가 같은 값을 가지고 있는지 판단하고 B가 대응하는 하위 나무가 없으면 바로 True로 돌아갈 수 있다.

    코드

    # -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        def is_subtree(self, pRoot1, pRoot2):
            if not pRoot2: return True
            if not pRoot1: return False
            if pRoot1.val == pRoot2.val:
                return self.is_subtree(pRoot1.left, pRoot2.left) and \
                       self.is_subtree(pRoot1.right, pRoot2.right)
            else: return False
        def HasSubtree(self, pRoot1, pRoot2):
            # write code here
            if (not pRoot1) or (not pRoot2): return False
            return self.is_subtree(pRoot1, pRoot2) or \
                   self.HasSubtree(pRoot1.left, pRoot2) or \
                   self.HasSubtree(pRoot1.right, pRoot2)
    

    코드 번역 우객망 모 큰 소의 C++ 코드는 단락 특성이라는 기교를 사용했다
  • 논리 연산자의 단락 특성(java를 예로 들면)
  • &&의 단락 특성: 프로그램이 왼쪽에서 오른쪽으로 실행되기 때문에 왼쪽이false라고 판단할 때 &&의 반환 결과는false로 정해져 있기 때문에 뒤의 판단 컴퓨터는 실행하지 않습니다
  • ||의 단락 특성: 프로그램은 왼쪽에서 오른쪽으로 실행되기 때문에 왼쪽이true라고 판단할 때 결과를 되돌려주는 것은true로 정해져 있기 때문에 뒤의 판단 컴퓨터는 실행하지 않습니다

  • 참고

  • https://www.nowcoder.com/questionTerminal/6e196c44c7004d15b1610b9afca8bd88
  • https://blog.csdn.net/nepenthe_csdn/article/details/52348194
  • 좋은 웹페이지 즐겨찾기