[LeetCode] 298. Binary Tree Longest Consecutive Sequence

 이진 트리(binary tree)가 주어지고, 이진 트리의 노드(node)에서 각 노드의 val의 값이 1씩 증가하는 child로만 연결이 가능하고 가장 긴 path의 길이를 반환하면 된다. 재귀(Recursive)를 활용한 DFS(Depth First Search)로 풀었다. 

 

class Solution {
    private int M;
    public Solution() {
        M = 0;
    }

    private void dfs(TreeNode n, int cnt) {
        TreeNode l = n.left;
        TreeNode r = n.right;

        if (l != null) {
            if (n.val - l.val == -1) {
                dfs(l, cnt+1);
            } else {
                dfs(l, 1);
            }
        }
        if (r != null) {
            if (n.val - r.val == -1) {
                dfs(r, cnt+1);
            } else {
                dfs(r, 1);
            }
        }
        if (M < cnt) {
            M = cnt;
        }
    }
    public int longestConsecutive(TreeNode root) {
        TreeNode l = root.left;
        TreeNode r = root.right;
        
        if (l == null && r == null) {
            return 1;
        } else {
            if (l != null) {
                if (root.val - l.val == -1) {
                    dfs(l, 2);
                } else {
                    dfs(l, 1);
                }
            }
            if (r != null) {
                if (root.val - r.val == -1) {
                    dfs(r, 2);
                } else {
                    dfs(r, 1);
                }
            }
        }
        return M;
    }
}