LeetCode Queue Reconstruction by Height Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue. Note: The number of people is less than 1,100. Example

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

1. [7,0]插入第0个位置，数组为[7,0]
2. [7,1]插入第1个位置，数组为[7,0], [7,1]
3. [6,1]插入第1个位置，数组为[7,0], [6,1], [7,1]
4. [5,0]插入第0个位置，数组为[5,0], [7,0], [6,1], [7,1]
5. [5,2]插入第2个位置，数组为[5,0], [7,0], [5,2], [6,1], [7,1]
6. [4,4]插入第4个位置，数组为[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]

LeetCode Third Maximum Number Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n). Example 1:

Input: [3, 2, 1]
Output: 1
Explanation: The third maximum is 1.

Input: [1, 2]
Output: 2
Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

Input: [2, 2, 3, 1]
Output: 1
Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

LeetCode Nth Digit Find the n^th digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … Note: n is positive and will fit within the range of a 32-bit signed integer (n < 2³¹). Example 1:

Input:
3
Output:
3

Input:
11
Output:
Explanation:
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.

• 1~9：宽度为1，数字个数1*9
• 10~99：宽度为2，数字个数2*90
• 100~999：宽度为3，数字个数3*900
• …

543. Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

          1
         / \
        2   3
       / \     
      4   5    

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

本题要求一棵树的直径，树的直径的定义是树中任意两点间的最长距离。
任意两点间的最长路径有如下三种选择：

1. 经过根节点的最长路径
2. 在左子树中不经过根节点的最长路径
3. 在右子树中不经过根节点的最长路径

其中第1种情况比较好处理，必须经过根节点，又必须是最长路径，则路径长度肯定是左右子树的最大高度之和+1(根节点)。第2、3种情况就更好处理了，就是以左右孩子为根递归计算最长路径。
代码如下：

class Solution {
private:
    int getHeight(TreeNode* root)
    {
        if (!root)
            return 0;
        int lh = getHeight(root->left);
        int rh = getHeight(root->right);
        return 1 + max(lh, rh);
    }

public:
    int diameterOfBinaryTree(TreeNode* root)
    {
        if (!root)
            return 0;
        //int ans = 1 + getHeight(root->left) + getHeight(root->right); // 节点数
        int ans = getHeight(root->left) + getHeight(root->right); // 路径数
        ans = max(ans, diameterOfBinaryTree(root->left));
        ans = max(ans, diameterOfBinaryTree(root->right));
        return ans;
    }
};

本代码提交AC，用时22MS。

参考：http://www.geeksforgeeks.org/diameter-of-a-binary-tree/，这篇博客的路径是指节点数，而本题的路径是指边数，所以第12行不能再加1了。

以上代码递归的过程是从根节点往孩子节点递归，这样计算高层节点的高度时，其实已经计算过低层节点的高度了，后面递归到低层节点时，会重复计算。所以代码还可以优化，比如可以不断递归到叶子节点再返回，这样高层节点的高度就可以直接用低层节点的高度加1计算得到，可以省不少时间。

二刷。在求解路径的同时可计算高度，而且先递归到叶子，然后不断从往上走，代码如下：

class Solution {
public:
	int DiameterAndHeight(TreeNode* root, int &height) {
		if (root == NULL || (root->left == NULL && root->right == NULL)) {
			height = 0;
			return 0;
		}
		int left_height = 0, right_height = 0;
		int left_diameter = DiameterAndHeight(root->left, left_height);
		int right_diameter = DiameterAndHeight(root->right, right_height);
		height = max(left_height, right_height) + 1;
		int left_edge = root->left == NULL ? 0 : 1, right_edge = root->right == NULL ? 0 : 1;
		return max(max(left_diameter, right_diameter), left_height + right_height + left_edge + right_edge);
	}
	int diameterOfBinaryTree(TreeNode* root) {
		int height = 0;
		return DiameterAndHeight(root, height);
	}
};

本代码提交AC，用时8MS，快了不少。