intuitive Java DFS and BFS solution


  • 0
    S

    DFS solution:
    The main idea is using pre-order traversing of binary tree.

    public class BottomLeftValue {
        public static int findBottomLeftValue(TreeNode root) {
            Tuple nominee = new Tuple(0, root.val);    // restore the max depth so far and corresponding left most value on this depth
            int curDepth = 0;
            dfs(root, nominee, curDepth);
            return nominee.val;
        }
    
        public static class Tuple {
            int depth;
            int val;
            public Tuple(int d, int value) {
                depth = d;
                val = value;
            }
    
        }
    
        public static void dfs(TreeNode root, Tuple nominee, int curDepth) {
            if (root == null)
                return;
            dfs(root.left, nominee, curDepth+1);
            if (curDepth > nominee.depth) {
                nominee.val = root.val;
                nominee.depth = curDepth;
            }
            dfs(root.right, nominee, curDepth+1);
    
        }
    }
    

    BFS solution:
    The key point is using null as the terminator of each level.

    public static int bfsBottomLeftValue(TreeNode root) {
            Queue<TreeNode> q = new LinkedList<>();
            q.add(root);
            q.add(null);
            int firstNodeVal = 0;
            boolean flag = true;
            while (!q.isEmpty()) {
                TreeNode node = q.poll();
                if (node == null) { // end of this level
                    if (q.isEmpty())
                        break;
                    q.add(null);
                    flag = true;    // indicate next node is the first node of this level
                }
                else {
                    if (flag) {
                        firstNodeVal = node.val;
                        flag = false;
                    }
                    if (node.left != null)
                        q.add(node.left);
                    if (node.right != null)
                        q.add(node.right);
                }
            }
            return firstNodeVal;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.