剣指offer第2版——面接問題8(java)

面接問題8:ツリーの次のノード
トピックの説明:ツリーとノードの1つを指定します.シーケンスの次のノードを見つけて返してください.ツリー内のノードには、左右の子ノードだけでなく、親ノードへのポインタも含まれています.
解析:中間ループの特徴に基づいて、1つのノードの次のノードの3つのケースを見つけます.
ケース1、右の子の木がある場合は、右の子を次の遍歴(探しているわけではない)ノードとして、そのノードの左の子の木に沿って(もしあれば)
出発して、葉ノードに出会うまで、その葉ノードは次の探しているノードです. 
ケース2:右サブツリーがない
①このノードは親ノードの左の子であり、そうであれば次のノードが親ノードである. 
②親ノードでない左の子は、親ノードを次の遍歴ノードとして遡上し、親ノードが親ノードでないか、またはノードが親ノードの左の子であるかが見つかるまで、その位置の親ノードは探す点となる
コード:

// 2019-06-14
public class Q8 {
	public static void main(String[] args) {
		ListNode1 node = getTree();
		ListNode1 next = getNext(node);
		// 4 2 8 5 9 1 6 3 7 
		if(next!=null) {
			System.out.println(next.val);
		}
	}
	
	public static ListNode1 getNext(ListNode1 root) {
		//     
		if(root.right!=null) {
			ListNode1 temp = root.right;
			while(temp.left!=null) {
				temp = temp.left;
			}
			return temp;
		}
		
		//                  
		if(root.right==null && root.father.left==root) {
			return root.father;
		}
		
		//                
		if(root.right==null && root.father.right==root) {
			ListNode1 temp = root.father;
			while(temp.father!=null) {
				if(temp.father.left==temp) {
					return temp;
				}
				temp = temp.father;
			}
		}
		
		System.out.println("There are not next node");
		return null;
	}
}

// 2019-03-11
public class Q8 {
	public static void main(String[] args) {
		//        P65  ，a~i      ， 1~9
		ListNode head1 = new ListNode(1, null);
		ListNode node2 = new ListNode(2, head1);
		ListNode node3 = new ListNode(3, head1);
		head1.left = node2;
		head1.right = node3;
		ListNode node4  = new ListNode(4, node2);
		ListNode node5  = new ListNode(5, node2);
		node2.left = node4;
		node2.right = node5;
		ListNode node6  = new ListNode(6, node3);
		ListNode node7  = new ListNode(7, node3);
		node3.left = node6;
		node3.right = node7;
		ListNode node8  = new ListNode(8, node5);
		ListNode node9  = new ListNode(9, node5);
		node5.left = node8;
		node5.right = node9;
		
		//       
		head1.oTo(head1);

		
		ListNode node = findNext(node7);
		if(node == null) {System.out.println("null");}
		else {
			System.out.printf("
result:%d",node.val);
		}
	}
	
	public static ListNode findNext(ListNode node) {
		if(node == null) {
			return null;
		}
		ListNode temp = null;;
		
		//    ：     ——           
		if(node.right!=null) {
			temp = node.right;
			System.out.printf("
      :%d",temp.val);
			while(temp.left!=null) {
				temp = temp.left;
			}
			return temp;
			
		}
		//    ：      ，     
		else{
			temp = node;
			System.out.println("
     ");
			
			//           ，             ，  null
			if(temp.father==null) {
				return null;
			}
			
			//          ，       ，                ，          
			else {
				while(temp!=null) {
					if(temp.father!=null) {
						if(temp.father.left == temp) {
							return temp.father;
						}else {
							temp = temp.father;
						}
					}
					temp = temp.father;
				}
				return null;
			}
		}
	}
}