Binary Tree的题目总结(三)

这篇文章主要列举数组或者链表如何转换为二叉树。

1，Convert Sorted Array to Binary Search Tree
将一个有序数组变为二叉平衡树。

因为数组有序，我们通过二分法，依次将数组元素变为数节点，代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode root = null;
        int l = 0;
	    int r = nums.length - 1;
    	if(l <= r) {
	    	int m = l + (r - l) / 2;
		    root = new TreeNode(nums[m]);
		    root.left = sortedArrayToBST(Arrays.copyOfRange(nums, l, m));
		    root.right = sortedArrayToBST(Arrays.copyOfRange(nums, m + 1, nums.length));
	    }
	    return root;
    }
}

2，Convert Sorted List to Binary Search Tree
将一个有序的链表转变为二叉平衡树。

用快慢指针，得到链表中间元素，过程和数组的类似。代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
       if(head == null) return null;
	ListNode fast = head;
	ListNode slow = head;
	ListNode pre = null;
	while(fast != null && fast.next != null && fast.next.next != null) {
			pre = slow;
			slow = slow.next;
			fast = fast.next.next;
	}
	TreeNode root = new TreeNode(slow.val);
	if(pre != null) {
		pre.next = null;
		fast = head;
		root.left = sortedListToBST(fast);
	}
	root.right = sortedListToBST(slow.next);
	return root; 
    }
}

3，Flatten Binary Tree to Linked List
将一个二叉树变为一个链表
例如给定一个二叉树
         1
        / \
       2   5
      / \   \
     3   4   6
输出：
   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

通过深搜遍历二叉树，保留节点的右子树，将节点的right指向左子树，让后再将左子树指向右子树，当然这是一个递归的过程。代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root) {
        if(root == null) return;
        flatten(root.left);
        flatten(root.right);
        TreeNode left = root.left;
        TreeNode right = root.right;
        root.left = null;
        root.right = left;
        while(root.right != null){
            root = root.right;
        } 
        root.right = right;   
    }
}

我们还可以用堆栈，用先序遍历的方法依次保留二叉树节点，然后建立一颗只有右孩子的树，代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
	static LinkedList<Integer> sb;
	public static void flatten(TreeNode root) {
        Stack<TreeNode> stack=new Stack<TreeNode>();
        sb = new LinkedList<Integer>();
        
        if(root==null) return;
        stack.push(root);
        dfs(root, stack);
        for(int i=1; i<sb.size(); i++){
            root.right=new TreeNode(sb.get(i));
            root.left = null;
            root = root.right;
        }

    }
    public static void dfs(TreeNode root, Stack<TreeNode> stack){
        while(!stack.isEmpty()){
             TreeNode node=stack.pop();
             sb.add(node.val);
             if(node.right!=null){
                stack.push(node.right);   
             }
            if(node.left!=null){
                stack.push(node.left); 
             }
        }
        System.out.println(sb);
    }
}