PattySung

<解題>

使用後序遍歷方式來遍歷二叉樹，從樹的底部開始考慮深度。首先處理葉子節點，然後逐漸向上計算深度，直到找到具有最深葉子節點的子樹的根節點。


class Solution {
    int maxDepth=-1;
    TreeNode result=null;
    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        postOrder(root,0);
        return result;
    }
    int postOrder(TreeNode node, int depth){
        if(node==null) return depth;
        int left = postOrder(node.left, depth+1);
        int right = postOrder(node.right, depth+1);

        if(left==right){
            maxDepth=Math.max(maxDepth,left);
            if(maxDepth ==left){
                result = node;
            }
        }
        return Math.max(left,right);
    }
}

Time: O(n) Space: O(n)

Leetcode-865. Smallest Subtree with all the Deepest Nodes

<解題>