.leetcode(513. Find Bottom Left Tree Value)

https://leetcode.com/problems/find-bottom-left-tree-value/

 

1. 2022.02.06 시도

소요시간: 18분(전역변수), 10분(bfs)

// 전역변수
class Solution {
    private int maxDepth = -1;
    private int max = Integer.MIN_VALUE;
    public int findBottomLeftValue(TreeNode root) {
        dfs(root, 0);
        return max;
    }
    
    private void dfs(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        
        dfs(root.left, depth+1);
        dfs(root.right, depth+1);
    
        if (root.left == null && root.right == null && maxDepth < depth) {
            maxDepth = depth;
            max = root.val;
            return;
        }
    }
}

// bfs
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int max = Integer.MIN_VALUE;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int length = queue.size();
            for (int i=0; i<length; i++) {
                TreeNode node = queue.poll();
                
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                if (i==0) {
                    max = node.val;
                }
            }
        }
        
        return max;
    }
}

풀이 접근 과정

전역변수에 depth와 max를 저장해두고 비교하면 쉽게 풀릴 것이라는 생각이 들었다.

너비 우선 탐색으로 하면 업렵지않게 max를 구할 수도 있다. 저번시간에 queue를 소비하는 방법에 배운것이 생각난다. 너비 우선으로 할때는 queue갯수만큼 for문을 돌려서 한층씩 내려가는 기술이 있다.

 

느낀점

• bfs는 queue의 특성을 이해하고 사용하니 쉽게 풀렸다.
• dfs는 한쪽부터(왼쪽부터) 읽는 것을 특징으로 삼아 문제를 푼 케이스다.
• dfs를 전역변수로 쓰지않고 풀기위해 클래스 선언을 해서 추가로 풀어보았다.

public class DepthAndMax {
    int max;
    int depth;
    
    DepthAndMax(int max, int depth) {
        this.max = max;
        this.depth = depth;
    }
}

class Solution {
    public int findBottomLeftValue(TreeNode root) {
       return dfs(root, 0).max;
    }
    
    private DepthAndMax dfs(TreeNode root, int depth) {
        if (root == null) {
            return new DepthAndMax(Integer.MIN_VALUE, depth-1);
        }
        
        if (root.left == null && root.right == null) {
            return new DepthAndMax(root.val, depth);
        }
            
        DepthAndMax left = dfs(root.left, depth+1);
        DepthAndMax right = dfs(root.right, depth+1);
        if (left.depth >= right.depth) {
            return left;
        } else {
            return right;
        }
        
    }
}

• 다른 사람들 푼걸 보니 전역변수를 쓰지 않고 리턴을 2개해야하는 경우, 리턴을 변형하지 않고 파라미터에 array를 추가하는 방식도 있다.

// https://leetcode.com/problems/find-bottom-left-tree-value/discuss/98802/Simple-Java-Solution-beats-100.0!
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        int [] ret = new int[]{ 0, 0 };
        dfs(root, 1, ret);
        return ret[0];
    }
    
    private void dfs(TreeNode root, int depth, int[] ret) {
        if (depth > ret[1]) {
            ret[0] = root.val;
            ret[1] = depth;
        }
        
        if (root.left != null) {
            dfs(root.left, depth+1, ret);
        }
        if (root.right != null) {
            dfs(root.right, depth+1, ret);
        }
    }
}

• bfs도 오른쪽부터 큐를 넣으면 훨씬 간단하게 마지막 leftmos를 구할 수 있다.

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            root = queue.poll();
            if (root.right != null) {
                queue.offer(root.right);
            }
            if (root.left != null) {
                queue.offer(root.left);
            }
        }
        
        return root.val;
    }
}

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형