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，快了不少。

LeetCode Path Sum III You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes). The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000. Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1
Return 3. The paths that sum to 8 are:
1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Example:

BSTIterator iterator = new BSTIterator(root);
iterator.next();    // return 3
iterator.next();    // return 7
iterator.hasNext(); // return true
iterator.next();    // return 9
iterator.hasNext(); // return true
iterator.next();    // return 15
iterator.hasNext(); // return true
iterator.next();    // return 20
iterator.hasNext(); // return false

Note:

• next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
• You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.

本题要求设计一个二叉搜索树的迭代器，迭代的输出当前树中最小值，并且要求next和hasNext是O(1)时间复杂度和O(h)空间复杂度，h为树的高度。 因为二叉搜索树的中序遍历是递增有序的序列，所以如果没有O(h)空间复杂度限制，则可以提前保存中序遍历结果，然后实现对数组的迭代器。但是这样的空间复杂度就是O(sizeof(tree))，不符合题意。 立马想到树的中序遍历的非递归实现，我们可以借助一个堆栈，先只把树的根和最左边的数压栈，这样栈顶元素就是树的最下角元素，也就是最小值。每调用一次next，返回当前栈顶元素，同时把栈顶元素的右孩子及右孩子的所有最左边的节点压栈。hasNext就好办，直接返回堆栈是否为空。 这样堆栈中最多会保存树高个数的节点，所以是O(h)的空间复杂度。完整代码如下：

class BSTIterator {
private:
    stack<TreeNode*> tree;
    void putAllLeft(TreeNode* root, stack<TreeNode*>& tree)
    {
        while (root != NULL) {
            tree.push(root);
            root = root->left;
        }
    }
public:
    BSTIterator(TreeNode* root) { putAllLeft(root, tree); } /** @return whether we have a next smallest number */
    bool hasNext() { return !tree.empty(); } /** @return the next smallest number */
    int next()
    {
        TreeNode* top = tree.top();
        tree.pop();
        putAllLeft(top->right, tree);
        return top->val;
    }
};

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