学步园

public class Test {
    
	public Node root;
	
	public void insert(int value){
		root = insert(root,value);
	}
	
	public Node insert(Node node,int value){
		if(node == null){
			node = new Node(value);
		}else if(node.value > value){
			node.left = insert(node.left,value);
		}else{
			node.right = insert(node.right,value);
		}
		return node;
	}
	
	public void print(Node node){
		if(node != null){
			print(node.left);
			System.out.println(node.value);
			print(node.right);
		}
	}
	
	public void turn(Node node){
		if(node != null){
			
			turn(node.left);
			turn(node.right);
			//左右2个排序链表  连接起来即可
			//注意叶子节点情况
			Node temp = node.left;
			while(temp != null){
				if(temp.right == null){
					break;
				}else{
					temp = temp.right;
				}
			}
			
			if (temp != null) {
				node.left = temp;
				temp.right = node;
			}
			
			temp = node.right;
			while(temp != null){
				if(temp.left == null){
					break;
				}else{
					temp = temp.left;
				}
			}
			
			if (temp != null) {
				node.right = temp;
				temp.left = node;
			}
		}
	}
	
	public static void main(String[] args){
		Test t = new Test();
		int[] a = {10,6,14,4,8,12,16};
		for(int i = 0; i < a.length; i++){
			t.insert(a[i]);
		}
		
		Node node = t.root;
		t.turn(node);
	
		System.out.println(t.root.value);
		System.out.println(t.root.left.value);
		System.out.println(t.root.left.left.value);
		System.out.println(t.root.left.left.left.value);
	}
	
}

树是：  10

          6        14

4           8   12       16 

程序输出为10 8 6 4

是否存在和为sum的路径？

public boolean hasPath(Node node,int sum){
		if(node == null){
			return false;
		}
		if(node.value == sum){
			return true;
		}
		return hasPath(node.left,sum - node.value) ||
			   hasPath(node.right,sum - node.value);
	}