ツリーを並べ替えた双方向チェーンテーブルに変換

質問:
ツリーを2つのフォークで検索し、ソートされた双方向チェーンテーブルに変換するには、追加の空間を使用できないことが要求されます(定数空間は許可されています).
例:
この二叉ルックアップツリーの双方向チェーンテーブル構造は,1＝3＝4＝6＝7＝8＝10＝13＝14である.
分析:
二叉ルックアップツリーは非常に鮮明な再帰構造を有しているため,この問題を解決する際に再帰を用いることを避けることができない.肝心なのはどのように再帰するかです.
1つのノードは常に1つの左ノードと右ノード(存在する場合)があるため、ノードNに対して、左ノードのサブツリーの最大値をNに返す限り、その最大値はNの前のノードであり、例えばノード8に対して、その左ノードのサブツリーの最大値は7であり、ノード8の前のノードは7であり、同様に、ノード7の次のノードは8である.右ノードのサブツリーについても同様です.このような考え方があれば、コードを書くのは難しいことではありません.

public class TreeToList {
	
	public static void main(String[] args) {
		Node a = new Node(18);
		Node b = new Node(8);
		Node c = new Node(15);
		Node d = new Node(5);
		Node e = new Node(60);
		Node f = new Node(50);
		Node g = new Node(65);
		Node h = new Node(68);
		
		a.left = b;
		b.left = d;
		b.right = c;
		a.right = e;
		e.left = f;
		e.right = g;
		g.right = h;
		
		Node t = convertNode(a, true);
		while(t != null) {
			System.out.println(t.value);
			t = t.right;
		}
		
	}
	
	// isRight is used to check nd is 
	// in the right subtree or left substree
	static Node convertNode(Node nd, boolean isRight) {
		if (nd == null) return null;
		
		Node pLeft = null;
		Node pRight = null;
		
		if (nd.left != null) {
			pLeft = convertNode(nd.left, false);
			pLeft.right = nd;
			nd.left = pLeft;
		}
		
		if (nd.right != null) {
			pRight = convertNode(nd.right, true);
			pRight.left = nd;
			nd.right = pRight;
		}
		
		Node temp = nd;
		if (isRight) {
			while (temp.left != null) {
				temp = temp.left;
			}
		} else {
			while (temp.right != null) {
				temp = temp.right;
			}
		}
		return temp;
	}
}

class Node {
	int value;
	Node left;
	Node right;	
	
	Node(int value) {
		this.value = value;
		left = null;
		right = null;
	}
}

転載出典を明記してください:http://blog.csdn.net/beiyeqingteng
参照先:http://zhedahht.blog.163.com/blog/static/254111742007127104759245/