BFS JAVA solution, find the first node in each as a candidate


  • 0
    P

    /**

    • Definition for a binary tree node.

    • public class TreeNode {

    • int val;
      
    • TreeNode left;
      
    • TreeNode right;
      
    • TreeNode(int x) { val = x; }
      
    • }
      */
      class Solution {
      // bfs
      // the first node of the next line will replace the current candidate
      // return the last candidate
      public int findBottomLeftValue(TreeNode root) {
      Queue<TreeNode> queue = new LinkedList<TreeNode>();
      queue.offer(root);
      int candidate = root.val;
      int curCount = 1;
      int nextCount = 0;
      boolean isNextFirst = false;

       while(!queue.isEmpty()) {
           TreeNode node = queue.poll();
           if(isNextFirst) candidate = node.val;
           curCount--;
           
           if(node.left != null) {
               queue.offer(node.left);
               nextCount++;
           }
           
           if(node.right != null) {
               queue.offer(node.right);
               nextCount++;
           }
           
           if(curCount == 0) {
               curCount = nextCount;
               nextCount = 0;
               isNextFirst = true;
           } else {
               isNextFirst = false;
           }
       }
       
       return candidate;
      

      }
      }


Log in to reply
 

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