P150 二叉树的直径

描述#

这个题目说的是，给你一棵二叉树，你要计算出这棵树的直径。二叉树的直径定义为树上任意两个节点之间最长路径的长度。其中，两个节点之间的路径不一定要经过根节点。

比如说，给你的二叉树是：
 0
/ \

1   2
/ 

4   8
在这棵二叉树中，最长的路径有两条，分别为 [4, 1, 0, 2] 和 [8, 1, 0, 2]，长度都为 3，因此你要返回的直径就是 3。
注意，直径的大小由两个节点之间边的数量来表示。在这个例子中，最长的两条路径上都有 3 条边，因此直径为 3。

代码#

public class AlgoCasts {
  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

  private int maxDepth(TreeNode root, int[] d) {
    if (root == null) return 0;
    int left = maxDepth(root.left, d);
    int right = maxDepth(root.right, d);
    d[0] = Math.max(d[0], left + right);
    return Math.max(left, right) + 1;
  }

  // Time: O(n), Space: O(n)
  public int diameterOfBinaryTreeRecursive(TreeNode root) {
    int[] d = new int[1];
    maxDepth(root, d);
    return d[0];
  }

  // Time: O(n), Space: O(n)
  public int diameterOfBinaryTreeIterative(TreeNode root) {
    if (root == null) return 0;
    int diameter = 0;
    Map<TreeNode, Integer> depthMap = new HashMap<>();
    Stack<TreeNode> st = new Stack<>();
    st.push(root);
    while (!st.empty()) {
      TreeNode node = st.peek();
      if (node.left != null && !depthMap.containsKey(node.left)) {
        st.push(node.left);
      } else if (node.right != null && !depthMap.containsKey(node.right)) {
        st.push(node.right);
      } else {
        st.pop();
        int left = depthMap.getOrDefault(node.left, 0);
        int right = depthMap.getOrDefault(node.right, 0);
        diameter = Math.max(diameter, left + right);
        depthMap.put(node, Math.max(left, right) + 1);
      }
    }
    return diameter;
  }

}