构建二叉树

问题1

根据前序和后序构建二叉树

原理

• 前序遍历为：根左右；后序遍历为：左右根

代码

注意事项

问题2

根据前序和中序构建二叉树

原理

代码

注意事项

问题3

根据中序和后序构建二叉树

原理

代码

注意事项

问题4

根据二叉排序树的后序构建二叉树

原理

代码

注意事项

问题5

将有序数组转换为二叉搜索树

原理

• 数组的中间节点为根节点
• 数据的第0个至mid-1个为左子树节点，数组的mid+1至length为右子树节点

代码

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
       if(nums==null||nums.length<=0){
           return null;
       }
       TreeNode root = new TreeNode(nums[nums.length/2]);
       root.left = sortedArrayToBST(Arrays.copyOfRange(nums,0,nums.length/2));
       root.right = sortedArrayToBST(Arrays.copyOfRange(nums,nums.length/2+1,nums.length));
       return root;
    }
}

注意事项

• Arrays.copyOfRange(arr,start,end);注意不包含end，和string.subString(str,start,end)类似。

问题6

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

原理

• 首先，这个问题很类似链表的归并排序。可以从这里入手
• 其次，通过快慢指针找到左子树和右子树，这里需要注意的是mid节点
• 最后，通过构建左右子树，恢复二叉树

代码

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head==null){
            return null;
        }
       if(head.next==null){
            return  new TreeNode(head.val,null,null);
        }
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = null;
        while(fast!=null&&fast.next!=null){
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;
        TreeNode left =  sortedListToBST(head);
        TreeNode right =  sortedListToBST(slow.next);
        TreeNode newRoot = new TreeNode(slow.val,left,right);
        return newRoot;
    }

   
}

注意事项

• 右子树的节点为slow.next
• 当只有一个节点的时候，直接创建一个树节点。