두 갈래 나무의 거울 문제

1099 단어 두 갈래 나무
이원 찾기 트리를 입력하여 이 트리를 거울로 변환합니다. 즉, 변환된 이원 찾기 트리에서 왼쪽 트리의 결점이 오른쪽 트리의 결점보다 큽니다.반복과 순환 두 가지 방법으로 트리의 거울 변환을 완성합니다.
분석:
(1) 귀속의 사상은 매우 간단하다. 만약에 왼쪽 나무와 오른쪽 나무가 모두 거울 전환을 완성했다면 뿌리 노드 아래의 순서를 직접 교환하면 전체 나무가 거울 전환을 완성할 수 있다.
(2) 순환: 문제는 실제로 각 노드의 아이의 좌우 순서를 교환해야 하기 때문에 광범위한 우선순위로 한 번 훑어보면 되고 해답을 구하는 과정에서 대기열을 보조 데이터 구조로 해야 한다.
//  ( )

public void mirror(Node root) {

  if (root == null||root.left == null || root.right == null) {
return;   }   // System.out.print(root.data);   Node temp = root.left;   root.left = root.right;   root.right = temp;   //   if (root.left!=null) {    mirror(root.left);   }if (root.right!=null) {    mirror(root.right);   } }

//두 갈래 트리의 미러링(순환 방식 구현)public void mirror1(Node root) {LinkedListqueue=New LinkedList<>();queue.add(root);while(queue.size()!=0) {//System.out.print(root.data);Node node=que.removeFirst();if(node.left!=null)que.add(node.left);if(node.right!=null)       queue.add(node.right);     Node temp = node.left;     node.left = node.right;     node.right = temp;   } }

좋은 웹페이지 즐겨찾기