/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        int depth = 0; // 記錄目前所在 node 的深度
        int maxDepth = 0; // 記錄目前所到最深的深度
        int[] tuple = new int[]{depth, maxDepth};

        recTraverse(root, tuple);

        return tuple[1];
    }

    private void recTraverse(TreeNode root, int[] tuple) {
        if (root == null) {
            return;
        }

        // recTraverse 每呼叫一次表示到新的一層深度所以 depth + 1
        tuple[0]++;
        // 如果目前到達的 depth > maxDepth, maxDepth 用新的 depth 取代
        if (tuple[0] > tuple[1]) {
             tuple[1] = tuple[0];
        }

        if (root.left == null && root.right == null) {
            return;
        }

        if (root.left != null) {
            recTraverse(root.left, tuple);
            // 因為從下一層回來, 所以 depth - 1
            tuple[0]--;
        }

        if (root.right != null) {
            recTraverse(root.right, tuple);
            // 因為從下一層回來, 所以 depth - 1
            tuple[0]--;
        }
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    maxDepth := recMaxDepth(root, 0, 0)

    return maxDepth
}

func recMaxDepth(node *TreeNode, currentDepth int, maxDepth int) int {
    currentDepth++
    if currentDepth > maxDepth {
        maxDepth = currentDepth
    }

    if (node.Left == nil && node.Right == nil) {
        return  maxDepth
    }

    if (node.Left != nil) {
        maxDepth = recMaxDepth(node.Left, currentDepth, maxDepth)
    }
    if (node.Right != nil) {
        maxDepth = recMaxDepth(node.Right, currentDepth, maxDepth)
    }

    return maxDepth
}