题解 | JAVA #二叉树的直径# [P3]

每个node的max直径是(leftTreeHeight + rightTreeHeight).
设个Gobal var存目前看到的最大diameter. dfs返回当前node为root的treeHeight。

import java.util.*;

public class Solution {
    int diameter = 0;

    public int diameterOfBinaryTree (TreeNode root) {
      dfs(root);
      return diameter;
    }
    
    // returns height of the tree 
    int dfs(TreeNode root) {
      if (root == null) return 0;
      int lh = dfs(root.left);
      int rh = dfs(root.right);
      int curDiameter = lh + rh;
      diameter = Math.max(curDiameter, diameter);
        
      return Math.max(lh, rh) + 1;
    }
}