一、543. 二叉树的直径

LeetCode：543. 二叉树的直径

二叉树的直径 = 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。

遇到二叉树的问题很容易去直接用求解的目标去定义递归函数。但是仔细考虑，返回树的直径并不能向上传播。因此我们可以拆分成两步：

• 树的直径 = 左儿子的高度 + 右儿子的高度 + 2

因此我们只需要求高度就行。

树求高度实际上是一个树形dp：dp[root] = max(dp[child]) +1

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        max_len = 0;
        height(root);
        return max_len;
    }
private:
    int height(TreeNode * root){
        if(!root) return -1;//没有结点时，高度为-1。有一个结点时，高度为0
        int left_height = height(root->left);//左儿子高度
        int right_height = height(root->right);//右儿子高度
        max_len = max(max_len, left_height + right_height + 2);
        return max(left_height, right_height) + 1;//返回以root为根的子树的高度。
    }
    int max_len;
};

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

LeetCode：108. 将有序数组转换为二叉搜索树

二叉搜索树（二叉查找树） ： 对于任意节点，其左子树的所有节点的值小于该节点的值，其右子树的所有节点的值大于等于该节点的值。
这里需要注意的是，题目所给的nums 按 严格递增 顺序排列。因此，我们可以根据平衡二叉查找树的性质（左右子树高度差不大于1），通过下标直接找到根结点的位置（中间位置的结点）。

• 当总结点个数为奇数时，中间位置的结点左右两边的结点个数相同，很显然左右子树结点个数相同，采用相同形状则高度是相同的。
• 当总结点个数为偶数时，中间位置的结点右边的结点个数 比 左边结点个数多1。对于本中间位置结点而言，由于左右子树的生成规则相同，右子树的高度最多比左子树的高度多1。
• 程序递归执行，因此所有结点皆满足这样的性质，则可以构建一颗平衡二叉树。

类似于：构建完全二叉查找树

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return createTree(nums, 0, nums.size()-1);
    }
private:
    TreeNode * createTree(vector<int> & nums, int L, int R){
        if(L > R) return nullptr;
        int mid = (L + R) >> 1;
        TreeNode * root = new TreeNode(nums[mid], createTree(nums, L, mid - 1), createTree(nums, mid + 1, R));
        return root;
    }
};