leetcode 두 갈래 나무 관련 작업의 총결
14274 단어 LetCode Tree
두 갈래 나무의 조작에서 가장 보편적인 것은 바로 귀속이다. 앞과 뒤의 순서가 두루 있고 순서가 두루 있다.앞뒤 순서가 반복되면 귀환을 사용할 수도 있고 자신의 창고로 귀환을 대체할 수도 있다.층층이 한 대열로 옮겨다니며, 층마다 상층의 모든 노드의 아이들이 보조한다.이 과정에서 각 층에 포함된 노드와 개수를 기록할 수 있다.
역귀적으로 문제를 해결하려면 세 가지 요소가 있다. 첫째, 그들 사이에 역귀관계가 있다는 것을 확인해야 한다. 대규모의 문제는 소규모 문제에서 일정한 전환 관계를 통해 해결된다.귀속은 무한히 귀속될 수 없기 때문에 반드시 끝날 조건이 있어야 한다.나무는 일반적으로 잎사귀 노드에 도달한다.그리고 귀환은 귀환에서 탈퇴할 수 있는 조건이 있다.
귀속의 해법은 일반적으로 모두 비귀속의 방식으로 대체할 수 있다.귀속은 시스템 호출 창고에 임시 저장된 것과 맞기 때문이다.그러면 우리는 시스템 창고의 기능을 대체하기 위해 창고를 스스로 설정할 수 있다.다만 가끔은 귀찮을 때가 있다.
만약 전체 트리에 대한 조작이라면 사실은 나무의 노드를 두루 훑어보는 것과 같다. 그러면 너의 조작은 앞의 순서와 뒤의 순서 방식에 대응하는 것이다.이러한 방식에 대해 사실 방문 노드의 순서도 확정되었다.visit(root.left) root.val visit(root.right) 순서는 두 갈래 검색 트리의 노드가 작은 것부터 큰 것까지 가치가 있는 순서입니다.visit(root.right) root.val visit(root.left)는 큰 순서에서 작은 순서로 바뀝니다.
뒷순서는 대체적으로 밑에서 위로 옮겨간다. 모든 자수에 대해 뿌리의 왼쪽 자수는 밑에서 위로 올라가고 그 다음에 뿌리의 오른쪽 자수는 밑에서 위로 올라간다.이 나무 뿌리를 방문한 후 위로 올라갔다.뒷순서가 모든 노드를 두루 방문할 때, 오른쪽 아이가null이거나, 오른쪽 아이가 방금 방문한 이전 노드이다.
맨 왼쪽 열을 순서대로 입고한 다음 순환을 시작합니다. 만약 창고가 비어 있지 않으면, 출고합니다. 만약 이 노드의 오른쪽 아이가 비어 있거나, 지난번에 방문한 노드가 있다면, 이 노드를 방문하십시오.만약 그렇지 않다면, 선후순으로 그의 오른쪽 아이를 방문해야 한다. 먼저 그것을 창고에 넣고, 그 다음에 r->r.right, 그리고 다시 순환해서 아이가 창고에 들어간 후에 다시 순환한다
먼저 순서대로 훑어보는 것은 맨 왼쪽의 열을 순서대로 방문한 후 입고하는 것과 같다. 그리고 출고 r->r.right는 그들의 오른쪽 아이를 찾는다. 오른쪽 아이는 입고하지 않고 같은 방식으로 오른쪽 나무를 방문한다.
중순번은 선순번과 유사하다. 단지 맨 왼쪽의 열을 순서대로 창고에 넣은 다음에 창고를 나가서 방문한 다음에 r->r.right가 그들의 오른쪽 아이를 찾으면 오른쪽 아이는 창고에 들어가지 않고, 그 다음에 같은 방식으로 오른쪽 나무를 방문한다.오른쪽 아이를 찾아 다음 순환에 들어가는 것은 오른쪽 아이를 똑같은 중순으로 훑어보는 것과 같다. 다음 순환은 노드가 비어 있으면 오른쪽 아이가 없으면 이전 하위 나무가 방문한 것과 같다.창고에서 나와 상층으로 들어갑니다. 만약 창고가 비어 있다면, 이것은 마지막 오른쪽 트리가 방문한 것입니다.
두 갈래 트리의 비귀속 반복 방식에 대해 링크를 클릭하여 쓰는 것이 비교적 상세합니다
1. 두 갈래 나무가 같은지 판단
두 갈래 나무는 뿌리와 좌우 두 개의 두 갈래 나무로 구성되어 있기 때문에 두 갈래 나무가 같은지 아닌지는 그들의 뿌리 값이 같은지, 왼쪽 나무와 오른쪽 나무가 동시에 같은지 판단한다.좌우자수가 같은지 아닌지를 판단하는 것은 또 같은 논리다.그래서 이것이 전형적인 귀속 판단 문제다.귀착의 경계는 바로 잎사귀의 노드를 판단하는 것이다.잎 노드의 특징은 바로 루트다.left==null&&root.right==null;귀속을 종료하는 조건은 두 나무의 뿌리 값이 같지 않다는 것이다.코드는 다음과 같습니다.
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null&&q==null)return true;
if((p==null)||(q==null))return false;
if(p.val==q.val){
return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
}
return false;
}public boolean isSameTree(TreeNode p, TreeNode q) {
Stack stack_p = new Stack <> ();
Stack stack_q = new Stack <> ();
if (p != null) stack_p.push( p ) ;
if (q != null) stack_q.push( q ) ;
while (!stack_p.isEmpty() && !stack_q.isEmpty()) {
TreeNode pn = stack_p.pop() ;
TreeNode qn = stack_q.pop() ;
if (pn.val != qn.val) return false ;
if (pn.right != null) stack_p.push(pn.right) ;
if (qn.right != null) stack_q.push(qn.right) ;
if (stack_p.size() != stack_q.size()) return false ;
if (pn.left != null) stack_p.push(pn.left) ;
if (qn.left != null) stack_q.push(qn.left) ;
if (stack_p.size() != stack_q.size()) return false ;
}
return stack_p.size() == stack_q.size() ;
} 두 갈래 나무가 대칭이면 다음과 같은 성질을 만족시켜야 한다. 좌우 나무는 거울면 대칭, 즉 중심 대칭이다.두 나무가 거울 대칭인지 아닌지를 판단하려면 뿌리가 같고 왼쪽의 왼쪽 나무와 오른쪽의 오른쪽 나무가 거울 대칭이다. 왼쪽의 오른쪽 나무와 오른쪽의 왼쪽 나무가 거울 대칭이다.즉 뿌리가 수직인 선을 축선으로 하고 축은 대칭이다.
public boolean isSymmetric(TreeNode root) {
if(root == null)return true;
return isMirror(root.left,root.right);
}
public boolean isMirror(TreeNode p,TreeNode q){
if(p==null&&q==null)return true;
if(p==null||q==null)return false;
if(p.val!=q.val)return false;
return isMirror(p.left,q.right)&&isMirror(p.right,q.left);
}public boolean isSymmetric(TreeNode root) {
if(root==null) return true;
Stack stack = new Stack();
TreeNode left, right;
if(root.left!=null){
if(root.right==null) return false;
stack.push(root.left);
stack.push(root.right);
}
else if(root.right!=null){
return false;
}
while(!stack.empty()){
if(stack.size()%2!=0) return false;
right = stack.pop();
left = stack.pop();
if(right.val!=left.val) return false;
if(left.left!=null){
if(right.right==null) return false;
stack.push(left.left);
stack.push(right.right);
}
else if(right.right!=null){
return false;
}
if(left.right!=null){
if(right.left==null) return false;
stack.push(left.right);
stack.push(right.left);
}
else if(right.left!=null){
return false;
}
}
return true;
} 3. 두 갈래 나무의 최대 깊이(즉 깊이)를 구한다.
이 나무의 깊이는 max(왼쪽 나무, 오른쪽 나무)+1이다.귀속시키면 됩니다. 경계는 잎 노드입니다.
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
}ffs 깊이가 우선입니다. 매번 창고 작업 시 대응하는 깊이를 알아야 하기 때문에 추가 창고로 동기화 창고 작업 기록을 작성합니다.
public int maxDepth(TreeNode root) {
if(root == null) {
return 0;
}
Stack stack = new Stack<>();
Stack value = new Stack<>();
stack.push(root);
value.push(1);
int max = 0;
while(!stack.isEmpty()) {
TreeNode node = stack.pop();
int temp = value.pop();
max = Math.max(temp, max);
if(node.left != null) {
stack.push(node.left);
value.push(temp+1);
}
if(node.right != null) {
stack.push(node.right);
value.push(temp+1);
}
}
return max;
} public int maxDepth(TreeNode root) {
if(root == null) {
return 0;
}
Queue queue = new LinkedList<>();
queue.offer(root);
int count = 0;
while(!queue.isEmpty()) {
int size = queue.size();
while(size-- > 0) {
TreeNode node = queue.poll();
if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
}
count++;
}
return count;
} 두 갈래로 나무를 검색하는 왼쪽 트리의 모든 값은 뿌리보다 작고 오른쪽 트리의 모든 값은 뿌리보다 크다.그래서 우선 우리는 이 수조의 중간값mid를 찾았는데 그것이 바로 뿌리였다.그리고 수조의 왼쪽 부분은 왼쪽 나무를 구성하고 오른쪽 부분은 오른쪽 나무를 구성한다.이렇게 귀속되면 귀속의 경계는 바로 수조가 분몰될 때이다
public TreeNode sortedArrayToBST(int[] nums) {
return sortArray(nums,0,nums.length-1);
}
public TreeNode sortArray(int[] nums,int s,int e){
if(s > e)return null;
int mid = s + (e-s)/2;
TreeNode t = new TreeNode(nums[mid]);
t.left = sortArray(nums,s,mid-1);
t.right = sortArray(nums,mid+1,e);
return t;
}public TreeNode sortedArrayToBST(int[] nums) {
int len = nums.length;
if ( len == 0 ) { return null; }
TreeNode head = new TreeNode(0);
Stack nodeStack = new Stack() ;//
nodeStack.push(head);
Stack leftIndexStack = new Stack();
leftIndexStack.push(0);
Stack rightIndexStack = new Stack();
rightIndexStack.push(len-1);
while ( !nodeStack.isEmpty() ) {
TreeNode currNode = nodeStack.pop();
int left = leftIndexStack.pop();
int right = rightIndexStack.pop();
int mid = left + (right-left)/2; // avoid overflow
currNode.val = nums[mid];
if ( left <= mid-1 ) {
currNode.left = new TreeNode(0);
nodeStack.push(currNode.left);
leftIndexStack.push(left);
rightIndexStack.push(mid-1);
}
if ( mid+1 <= right ) {
currNode.right = new TreeNode(0);
nodeStack.push(currNode.right);
leftIndexStack.push(mid+1);
rightIndexStack.push(right);
}
}
return head;
} 5. 질서정연한 체인 테이블을 두 갈래 검색 트리로 바꾸기
먼저 유사한 수조가 두 갈래 나무의 사고방식을 바꾸려면 우리는 매번 체인표의 첫 번째 노드, 중간 노드와 끝 노드를 찾아야 한다.어떻게 빨리 찾을 수 있을까요
while(fast!=null&&fast.next!=null){
fast = fast.next.next;
slow = slow.next;
}public TreeNode sortedListToBST(ListNode head) {
ListNode tail = head;
if(head==null) return null;
while(tail.next!=null){
tail = tail.next;
}
return go(head,tail);
}
public TreeNode go(ListNode head,ListNode tail){
if(head==null)return null;
if(head==tail)return new TreeNode(head.val);
ListNode fast = head;
ListNode slow = head;
ListNode pre = null;
while(fast!=null&&fast.next!=null){
fast = fast.next.next;
pre = slow;
slow = slow.next;
}
if(pre!=null){
pre.next = null;
}else{
head = null;
}
TreeNode t = new TreeNode(slow.val);
t.left = go(head,pre);
t.right = go(slow.next,fast);
return t;
}만약 우리가 나무의 총 노드 수 n을 알고 있다면, 그것이 고도의 균형이라는 것을 알았다면, 이 나무의 형상은 이미 확정되었을 것이다.(0,n)(0,n/2)(n/2+1,n)으로...생성된 그룹 모양은 최종 모양입니다. 노드마다 값을 다시 채워야 합니다.그러면 저희가 중순으로 훑어보도록 하겠습니다.
노드를 만드는 순서는 그 나무를 중순으로 훑어보는 순서와 맞먹는다. 마침 중순으로 두 갈래 나무를 검색하는 수치 순서는 승차순 1, 2, 3, 4, 5, 6이다. 체인 테이블 순서에 딱 맞다. 체인 테이블 노드 값으로 트리 노드를 만들자.
private ListNode node;
public TreeNode sortedListToBST(ListNode head) {
if(head == null){
return null;
}
int size = 0;
ListNode runner = head;
node = head;
while(runner != null){
runner = runner.next;
size ++;
}
return inorder(0, size - 1);
}
public TreeNode inorder(int start, int end){
if(start > end){
return null;
}
int mid = start + (end - start) / 2;
TreeNode left = inorder(start, mid - 1);
TreeNode treenode = new TreeNode(node.val);
treenode.left = left;
node = node.next;
TreeNode right = inorder(mid + 1, end);
treenode.right = right;
return treenode;
}6. 차례차례 반복하는 방식 실현
public List> levelOrderBottom(TreeNode root) {
List> res = new ArrayList();
levelGo(res,root,0);
return res;
}
public void levelGo(List> list,TreeNode t,int level){
if(t==null) return;
if(list.size()<=level){
list.add(new ArrayList());
}
levelGo(list,t.left,level+1);
levelGo(list,t.right,level+1);
list.get(level).add(t.val);
}
public List> levelOrderBottom(TreeNode root) {
List> res = new ArrayList();
levelGo(res,root,1);
return res;
}
public void levelGo(List> list,TreeNode t,int level){
if(t==null) return;
if(list.size()());
}
levelGo(list,t.left,level+1);
levelGo(list,t.right,level+1);
list.get(list.size()-level).add(t.val);
}
모두 귀속 과정에서 이 노드가 있는 층수를 전달하고 그 층수에 따라 대응하는 동일한 위치에 놓는다.함수 파라미터를 통해 파라미터 중의 노드의 정보도 압축하는 것과 같다. 그 층으로 귀속되든지 간에 나는 함수 파라미터를 통해 현재 노드가 전체 트리에 대응하는 층수를 얻을 수 있다.
7. 나무 한 그루의 균형이 맞는지 판단한다
여기 균형의 정의는 각 노드의 두 개의 자수의 높이 차이가 1을 넘지 않는다는 것이다.
이 문제는 바로 나무를 훑어보고 각 노드의 좌우 나무의 높이를 구해 판단할 수 있다.만약 하나의 귀환을 사용한다면:
int depth (TreeNode root) {
if (root == null) return 0;
return max (depth(root.left), depth (root.right)) + 1;
}
bool isBalanced (TreeNode root) {
if (root == NULL) return true;
int left=depth(root.left);
int right=depth(root.right);
return abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}public boolean isBalanced(TreeNode root) {
if(root == null) return true;
return ban(root)!= -1;
}
public int ban(TreeNode t){
if(t == null)return 0;
int tl = ban(t.left);
if(tl == -1)return -1;
int tr = ban(t.right);
if(tr == -1)return -1;
if(tl - tr>1||tl-tr8. 두 갈래 나무의 가장 긴 경로를 찾아라
두 노드 사이의 연결 노선 길이가 1로 가장 긴 경로를 찾아내다
각 노드에 대응하는 최대 경로는 왼쪽 트리의 깊이에 오른쪽 트리의 깊이를 2로 하고 하나의 값으로 각 노드에 대응하는 가장 긴 경로 중의 비교적 큰 자를 기록한다. 이 노드의 깊이는 바로 좌우 트리의 깊이를 1로 한다.
좋은 웹페이지 즐겨찾기
