소잡이--검지offer-이차 수색 나무와 양방향 체인 시계

문제 설명
두 갈래 검색 트리를 입력하면 두 갈래 검색 트리를 정렬된 양방향 체인 테이블로 변환합니다.새 결점을 만들 수 없으며 트리에서 결점 포인터의 방향을 조정할 수 있습니다.
2. 문제 풀이의 방향
두 갈래 검색 트리를 쌍방향 체인 테이블로 바꾸는 것은 사실 중간 순서에 따라 두 갈래 트리를 훑어본 다음에 체인 테이블을 만드는 것이다. 이는 귀속과 비귀속 두 가지 방식으로 나눌 수 있다.
1. 귀속 방식
귀환 방식은 매번 귀환이 체인 시계의 머리 노드이기 때문에 새로운 요소를 추가하는 것은 체인 시계의 끝부분이고 현재 귀환이 체인 시계의 머리 노드이기 때문에 체인 시계를 끊임없이 좌우로 옮겨야 한다.
2. 비귀속 방식
창고 공간을 이용하여 해결하고 두 개의 TreeNode를 정의한다. 하나는 체인 테이블의 헤드 노드를 가리키고 다른 하나는 체인 테이블의 현재 노드 위치를 가리킨다.
코드

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    //TreeNode root=null;
    public TreeNode Convert(TreeNode pRootOfTree) {

// 
        if(pRootOfTree==null)
            return pRootOfTree;
        Stack stack=new Stack();
        TreeNode result=null;// 
        TreeNode cur=null;// 
        while(!stack.empty() || pRootOfTree!=null){
            while(pRootOfTree!=null){
                stack.push(pRootOfTree);
                pRootOfTree=pRootOfTree.left;
            }
            if(!stack.empty()){
                TreeNode tmp=stack.pop();
                if(result==null){
                    result=tmp;
                    cur=result;
                }else{
                    cur.right=tmp;
                    tmp.left=cur;
                    cur=cur.right;
                }
               pRootOfTree=tmp.right; 
            }
        }
        return result;

        /* 
        if(pRootOfTree==null)
            return pRootOfTree;
//  if(pRootOfTree.left==null && root==null){
      //      root=pRootOfTree; 
      //      return pRootOfTree;
      //  }else if(pRootOfTree.left==null && root!=null)
      //      return pRootOfTree;
        TreeNode left;
        TreeNode right;
        if(pRootOfTree.left==null)// ，left 
            left=pRootOfTree;
        else{
        // ， 
            left=Convert(pRootOfTree.left);
            // ， ， pRootOfTree 
            while(left!=null && left.right!=null)
            left=left.right;
        	left.right=pRootOfTree;
        	pRootOfTree.left=left;
        	left=left.right;
        }
        if(pRootOfTree.right==null){
            while(left!=null && left.left!=null)
                left=left.left;
            return left;
        }
        right=Convert(pRootOfTree.right);
        left.right=right;
        right.left=left;
        while(left!=null && left.left!=null)
            left=left.left;
        return left;    
        */
    }
}

다음은 귀속적인 방식으로 다시 실현된 것이다

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    TreeNode head = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null)
            return null;
        TreeNode result = convertCore(pRootOfTree);
        while(result.left != null)
            result = result.left;
        return result;
    }
    private TreeNode convertCore(TreeNode root){
        if(root == null){
            return null;
        }
        TreeNode left = convertCore(root.left);
        TreeNode right = convertCore(root.right);
        if(left != null){
            while(left.right!=null){
                left = left.right;
            }
            left.right = root;
            root.left = left;
        }
        if(right != null){
            while(right.left != null)
                right = right.left;
            right.left = root;
            root.right = right;
        }
        return root;
    }
}