构建二叉树

问题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
  • 当只有一个节点的时候,直接创建一个树节点。
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。