最大二叉树

传送门 https://leetcode-cn.com/problems/maximum-binary-tree/

题目描述

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：

二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。
右子树是通过数组中最大值右边部分构造出的最大二叉树。

通过给定的数组构建最大二叉树，并且输出这个树的根节点。

示例：

输入：[3,2,1,6,0,5]
输出：返回下面这棵树的根节点：

  6
/   \
3    5
\    / 
 2  0   
   \
    1

题解

思路：
题意清晰易懂，且明显可以看出解决问题方法是一个流程的重复，所以想到递归。
流程：

• 找数组特定范围内的最大值，和最大值对应的数组下标
• 将最大值添加的树结点
• 以数组最大值下标为分割点，在分割的两部分重复上面两步骤

class Solution {
    public TreeNode create(int begin, int end, int[] nums)
    {
        TreeNode node = null;
        
        // 只存下标有利于节省内存
        int index = begin;
        for (int i=begin; i<=end; i++)
        {
            if (nums[i] > nums[index])
            {
                index = i;
            }
        }
        
        //System.out.println(begin + " "+ index+ " " + end + " " + nums[index]);
        node = new TreeNode(nums[index]);
        
        if (index != begin )
        node.left = create( begin, index-1 , nums );
        
        if (index != end )
        node.right =  create( index+1 , end, nums ); 
    
        return node;
    }
    
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if ( nums.length == 0 )
            return null;
        return create(0, nums.length-1, nums);
    }
}

扩展

传送门 https://leetcode-cn.com/problems/maximum-binary-tree/

思路：
从题目样例中可以看出，数组是由给出的A树经过中序遍历，再加上附加值得到。然后创建最大树的方法与上面题解法完全一致。

class Solution {
    public void inTraverse(TreeNode node, List<Integer> list)
    {
        if ( node != null )
        {
            if ( node.left != null )
            {
                inTraverse( node.left, list );
            }
            list.add( node.val );
            if ( node.right != null )
            {
                inTraverse( node.right, list );
            }
        }
    }
    
    public TreeNode create( int begin, int end, List<Integer> list)
    {
        TreeNode node = null;
        int index = begin;
        
        for ( int i=begin; i<=end; i++ )
        {
            if (list.get(i) > list.get(index))
                index = i;
        }
        
        node = new TreeNode(list.get(index));
        
        if (index != begin)
            node.left = create( begin, index-1, list);
        if (index != end)
            node.right = create( index+1, end, list);
        
        return node;
    }
    
    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        List<Integer> list = new ArrayList<Integer>();
        inTraverse(root, list);
        list.add(val);
        return create(0, list.size()-1, list);
    }
}