Gidhub BE Developer

LeetCode : 104. Maximum Depth of Binary Tree

2020-11-11
goodGid

Maximum Depth of Binary Tree

Problem

Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Note: A leaf is a node with no children.

Example

Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7

Code (20. 11. 11)

public int maxDepth(TreeNode root) {
    return find(0, root);
}

public int find(int depth, TreeNode node) {
    if (node == null) {
        return depth;
    }
    return Math.max(find(depth + 1, node.left), find(depth + 1, node.right));
}
  • 머리 아팠다.

    오랜만에 재귀로 푸려니까 너무 어려웠다.


Code (21. 07. 14)

class Solution {

    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return getMaxDepth(root, 1);
    }

    public int getMaxDepth(TreeNode node, int ans) {
        if (node == null) {
            return ans;
        }

        int leftMaxDepth = 0;
        int rightMaxDepth = 0;

        if (node.left != null) {
            leftMaxDepth = getMaxDepth(node.left, ans + 1);
            System.out.println("leftMaxDepth : " + leftMaxDepth);
        }

        if (node.right != null) {
            rightMaxDepth = getMaxDepth(node.right, ans + 1);
            System.out.println("rightMaxDepth : " + rightMaxDepth);
        }

        ans = Math.max(ans, Math.max(leftMaxDepth, rightMaxDepth));

        return ans;
    }
}
  • LeetCode 웹 IDE에서 바로 풀었다.

    풀 수 있을까? 했는데 두드려보니 풀렸다.


Code (21. 09. 19) (x)

class Solution {
    public int maxDepth(TreeNode root) {
        return go(root,0,0);
    }
    
    private int go(TreeNode node, int depth, int ans) {
        if (node == null) {
            return depth;
        }
        
        ans = Math.max(ans, go(node.left, depth+1, ans));
        ans = Math.max(ans, go(node.right, depth+1, ans));
        
        return ans;
    }
}
  • 다시 풀 필요 X

Reference


Recommend

Index