654.最大二叉树

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

二叉树的根是数组中的最大元素。

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

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

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

Example 1:

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

                    6

          /                    \

        3                         5

            \                    /

                2             0

                    \

                        1

注意:

给定的数组的大小在 [1, 1000] 之间。

本质就是写出一个方法，找出数组最大值的位置，并且将值生成一个节点，然后递归左右子树。

C#代码：

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using static LeetCodeCShap2.Program;

namespace LeetCodeCShap2

{

    class Program

    {

        public class TreeNode

        {

            public int val;

            public TreeNode left;

            public TreeNode right;

            public TreeNode(int x) { val = x; }

        }

        static void Main(string[] args)

        {

            int[] nums = new int[] { 3, 2, 1, 6, 0, 5 };

            Program obj = new Program();

            TreeNode result = obj.ConstructMaximumBinaryTree(nums, 0, nums.Length);

            Console.WriteLine("根val为{0}",result.val);

            Console.ReadLine();

        }

        public TreeNode ConstructMaximumBinaryTree(int[] nums, int l , int r)

        {

            if (l == r)

            {

                return null;

            }

            int max = l;

            for (int i = l; i < r; i++)

            {

                if (nums[i] > nums[max])

                {

                    max = i;

                }

            }

            TreeNode root = new TreeNode(nums[max]);

            root.left = ConstructMaximumBinaryTree(nums, l, max);

            root.right = ConstructMaximumBinaryTree(nums, max+1, r);

            return root;

        }

    }

}