《검지offer》 - 두 갈래 나무의 다음 결점, 대칭 두 갈래 나무, 글자 순서에 따라 두 갈래 나무를 인쇄하고 두 갈래 나무를 여러 줄로 인쇄한다.

하나, 두 갈래 나무의 다음 결점:

1. 제목:
두 갈래 나무와 그 중의 한 결점을 정하십시오. 순서를 반복하는 다음 결점을 찾아 돌아오십시오.나무의 결점은 좌우 자결점뿐만 아니라 부모 결점을 가리키는 바늘도 포함하고 있음을 주의하십시오.
2. 문제 해결 방법:
두 갈래 나무의 다음 노드를 분석하면 모두 다음과 같은 상황이 있다. (1) 두 갈래 나무가 비어 있으면 다시 비어 있다.(2) 노드의 오른쪽 아이가 존재하면 하나의 지침을 설정하여 이 노드의 오른쪽 아이에서 출발하여 왼쪽 결점을 가리키는 지침을 따라 찾은 잎 노드가 바로 다음 노드이다.(3) 노드는 루트가 아닙니다.이 노드가 부모 노드의 왼쪽 아이라면 부모 노드로 돌아갑니다.그렇지 않으면 계속해서 아버지 노드의 아버지 노드를 훑어보고 세 번째 판단을 반복하여 결과를 되돌려줍니다.
3. 코드 구현:

public class Test15 {
	
	 public TreeLinkNode GetNext(TreeLinkNode pNode){
		 
		 if(pNode == null){
			 return null;
		 }
		 if(pNode.right != null){
			 pNode = pNode.right;
			 while(pNode.left!=null){
				 pNode = pNode.left;
			 }
			 return pNode;
		 }
		 while(pNode.next!=null){
			 TreeLinkNode parent = pNode.next;
			 if(parent.left==pNode){
				 return parent;
			 }
			 pNode = pNode.next;
		 }
		 return null;
    }
}

class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;// 
    TreeLinkNode(int val) {
        this.val = val;
    }
}

 

2. 대칭 두 갈래 나무:

1. 제목:
두 갈래 나무가 대칭적인지 아닌지를 판단하는 함수를 실현하세요.만약 두 갈래 나무가 이 두 갈래 나무와 같은 거울이라면 대칭으로 정의하십시오.
2. 문제 해결 방법:
가장 간단한 방법은 귀속 방식을 사용할 수 있지만, 귀속을 사용하면 이 문제의 가치를 발굴할 수 없기 때문에 우리는 DFS와 BFS를 사용할 수 있다.
3. 코드 구현:
(1) 첫 번째: 귀속 알고리즘:
① pRoot만 있으면left와 pRoot.right의 대칭 여부는 됩니다.
② 좌우 노드의 값이 같고 대칭 서브트리 left.left,right.right ;left.rigth,right.left도 대칭입니다.

public class Test16 {

	boolean isSymmetrical(TreeNode pRoot){
		if(pRoot == null) return true;
		return judge(pRoot.left,pRoot.right);
    }
	
	boolean judge(TreeNode leftNode,TreeNode rightNode){
		if(leftNode == null) return rightNode==null;
		if(rightNode == null) return false;
		if(leftNode.val != rightNode.val) return false;
		return judge(leftNode.left,rightNode.right) && judge(leftNode.right,rightNode.left);
	}
	
}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;

    }
}

(2) 두 번째 방법: DFS 깊이 우선 순위:
DFS는 스택을 사용하여 쌍의 노드를 저장합니다.
① 창고를 나갈 때도 짝짓기:
다 비우면 계속;
하나는 비어 있고false로 되돌아오기;
비어 있지 않고 현재 값을 비교합니다. 값이 같지 않으면false로 돌아갑니다.
② 입고순서를 정하고 매번 입고할 때마다 짝을 이룬다. 예를 들어 left.left,right.right ;left.rigth,right.left

	boolean isSymmetrical2(TreeNode pRoot){
		// ： ： Stack 
		if(pRoot==null) return true;
		
		Stack stack = new Stack<>();
		// 
		stack.push(pRoot.left);
		stack.push(pRoot.right);
		while(!stack.isEmpty()){
			// 
			TreeNode right = stack.pop();
			TreeNode left = stack.pop();
			if(left==null && right==null) continue;
			if(left==null ||right==null) return false;
			if(left.val!=right.val) return false;
			
			// ：
			stack.push(left.left);
			stack.push(right.right);
			stack.push(right.left);
			stack.push(left.right);
		}
		return true;
	}

(3) 세 번째 방법: BFS 폭 우선 순위:
BFS는 Queue를 사용하여 위의 코드와 매우 유사한 쌍의 노드를 저장합니다.
① 나갈 때도 짝짓기
다 비우면 계속;
하나는 비어 있고false로 되돌아오기;
비어 있지 않고 현재 값을 비교합니다. 값이 같지 않으면false로 돌아갑니다.
② 입단 순서를 정하고 매번 입단할 때마다 짝을 이룬다. 예를 들어 left.left,right.right ;left.rigth,right.left.

	boolean isSymmetrical3(TreeNode pRoot){
		// ： ： 
		if(pRoot==null) return true;
		Queue queue = new LinkedList<>();
		
		queue.offer(pRoot.left);
		queue.offer(pRoot.right);
		
		while(!queue.isEmpty()){
			// 
			TreeNode right = queue.poll();
			TreeNode left = queue.poll();
			
			if(left ==null && right ==null) continue;
			if(left==null || right==null) return false;
			if(left.val != right.val) return false;
			
			// 
			queue.offer(left.left);
			queue.offer(right.right);
			queue.offer(left.right);
			queue.offer(right.left);
		}
		return true;
	}

 

3. 두 갈래 트리를 글자순으로 인쇄합니다.

1. 제목:
함수는 지그재그로 두 갈래 트리를 인쇄합니다. 즉, 첫 번째 줄은 왼쪽에서 오른쪽으로, 두 번째 줄은 오른쪽에서 왼쪽으로, 세 번째 줄은 왼쪽에서 오른쪽으로, 다른 줄은 이와 같이 인쇄합니다.
2. 문제 해결 방법:
창고가 선진적으로 나온 성질을 이용하여 두 창고에 각각 홀수층과 짝수층의 노드를 저장한다.
3. 코드 구현:

public class Test18 {
	public ArrayList> Print(TreeNode pRoot) {
		int layer = 1;
		//s1 ：
		Stack s1 = new Stack();
		s1.push(pRoot);
		//s2 ：
		Stack s2 = new Stack();
		ArrayList> list = new ArrayList>();
		
		while(!s1.empty() || !s2.empty()){
			if(layer%2 !=0){
				// ：
				ArrayList temp = new ArrayList();
				while(!s1.empty()){
					TreeNode node = s1.pop();
					if(node!=null){
						temp.add(node.val);
						s2.push(node.left);
						s2.push(node.right);
					}
				}
				if(!temp.isEmpty()){
					list.add(temp);
					layer++;
				}
			}else{
				// ：
				ArrayList temp = new ArrayList();
				while(!s2.isEmpty()){
					TreeNode node = s2.pop();
					if(node!=null){
						temp.add(node.val);
						s1.push(node.right);
						s1.push(node.left);
					}
				}
				if(!temp.isEmpty()){
					list.add(temp);
					layer++;
				}
			}
		}
		return list;
    }
}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}

 

넷째, 두 갈래 나무를 여러 줄로 인쇄합니다.

1. 제목:
위에서 아래로 층별로 두 갈래 트리를 인쇄하고 같은 층의 결점은 왼쪽에서 오른쪽으로 출력합니다.층마다 줄을 출력합니다.
2. 코드 구현:

public class Test19 {
	
	 ArrayList> Print(TreeNode pRoot) {
		 ArrayList> result = new ArrayList>();
		 if(pRoot == null){
			 return result;
		 }
		 
		 Queue queue = new LinkedList();
		 ArrayList queueList = new ArrayList();
		 queue.add(pRoot);
		 int start = 0 ,end = 1;

		 while(!queue.isEmpty()){
			 TreeNode current = queue.remove();
			 queueList.add(current.val);
			 start++;
			 if(current.left!=null){
				 queue.add(current.left);
			 }
			 if(current.right!=null){
				 queue.add(current.right);
			 }
			 if(start == end){
				 end = queue.size();
				 start=0;
				 result.add(queueList);
				 queueList = new ArrayList();
			 }
			 
		 }
		 return result;
    }
}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}