一、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;
}
};