543. Diameter of Binary Tree - Easy

前往題目

之前寫的文章

思路

1. DFS
2. 每個點的左子樹與右子樹的長度加起來再加1(本身)

這題的關鍵是每個點都有可能是拐彎的點

Code

class Solution {
    int ret = 0;
    
    public int diameterOfBinaryTree(TreeNode root) {
        findDepth(root);
        return ret - 1; // Need edges count only
    }

    // DFS
    private int findDepth(TreeNode root) {
        if (root == null) return 0;
        
        // node counts
        int leftPath = findDepth(root.left);
        int rightPath = findDepth(root.right);

        // Current node as turning node
        ret = Math.max(ret, leftPath + 1 + rightPath);

        // return node count, so add 1 as current node
        return Math.max(leftPath, rightPath) + 1;
    }
}

2024/06/23

• 一段時間沒寫，dfs的感覺又沒了