Python 은 이 진 트 리 의 k 번 째 노드 기능 예 시 를 찾 습 니 다.

이 글 의 사례 는 Python 이 두 번 째 포크 검색 트 리 의 k 번 째 노드 기능 을 찾 는 것 을 실현 하 는 것 을 보 여 준다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
제목 설명
두 번 째 포크 검색 트 리 를 지정 하여 k 번 째 큰 노드 를 찾 습 니 다.

바로 중간 순서 로 옮 겨 다 니 는 과정 입 니 다.추가 적 인 배열 이 필요 하지 않 고 노드 에 편리 한 후에 k 를 하나 줄 이면 됩 니 다.
코드 1

class TreeNode:
  def __init__(self, x):
    self.val = x
    self.left = None
    self.right = None
class Solution:
  def __init__(self):
    self.k = 0
  def recursionKthNode(self, Root):
    result = None
    if result == None and Root.left:
      result = self.recursionKthNode(Root.left)
    if result == None:
      if self.k == 1:
        return Root
      self.k -= 1
    if result == None and Root.right:
      result = self.recursionKthNode(Root.right)
    return result
  def KthNode(self, Root, k):
    if Root == None:
      return None
    self.k = k
    return self.recursionKthNode(Root)
Root = TreeNode(5)
Root.left = TreeNode(3)
Root.left.left = TreeNode(2)
Root.left.right = TreeNode(4)
Root.right = TreeNode(7)
Root.right.left = TreeNode(6)
Root.right.right = TreeNode(8)
print(Solution().KthNode(Root,3).val)

output : 4
코드 2

class TreeNode:
  def __init__(self, x):
    self.val = x
    self.left = None
    self.right = None
class Solution:
  def __init__(self):
    self.k = 0
  def InOrder(self, Root):
    ans = None
    if Root:
      if ans == None and Root.left:
        ans = self.InOrder(Root.left)  #    
      if ans == None and self.k == 1:
        ans = Root           #       
      if ans == None and self.k != 1:   #         ,k--
        self.k -= 1
      if ans == None and Root.right:   #    
        ans = self.InOrder(Root.right)
    return ans
  def KthNode(self, Root, k):
    if Root == None or k <= 0:
      return None
    self.k = k
    return self.InOrder(Root)

Python 관련 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있 습 니 다.
본 논문 에서 말 한 것 이 여러분 의 Python 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.

좋은 웹페이지 즐겨찾기