Verbose Java Solution, Binary tree level order traversal


  • 26

    Typical way to do binary tree level order traversal. Only additional step is to remember the first element of each level.

    public class Solution {
        public int findLeftMostNode(TreeNode root) {
            if (root == null) return 0;
            
            int result = 0;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    TreeNode node = queue.poll();
                    if (i == 0) result = node.val;
                    if (node.left != null) queue.add(node.left);
                    if (node.right != null) queue.add(node.right);
                }
            }
            
            return result;
        }
    }
    

  • 0
    J

    @shawngao
    Does it work for the tree below? Correct answer is B.

    A
    

    /
    B C

    D

    I believe it needs a postorder traversal.


  • 0
    J

    @Jeff.Jing said in Verbose Java Solution, Binary tree level order traversal:

    @shawngao
    Does it work for the tree below? Correct answer is B.

    A
    

    /
    B C

    D

    I believe it needs a postorder traversal.

    After posted, it messed up the tree. A is root, has two child B & C, C has a right child D.


  • 0
    J

    @shawngao said in Verbose Java Solution, Binary tree level order traversal:

    Typical way to do binary tree level order traversal. Only additional step is to remember the first element of each level.

    public class Solution {
        public int findLeftMostNode(TreeNode root) {
            if (root == null) return 0;
            
            int result = 0;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    TreeNode node = queue.poll();
                    if (i == 0) result = node.val;
                    if (node.left != null) queue.add(node.left);
                    if (node.right != null) queue.add(node.right);
                }
            }
            
            return result;
        }
    }
    

    Checked the result with leetcode. your solution is right. It doesn't have to be the left leave. your solution is really neat.


  • 0
    W

    level order,but first add right child,then add left child。and change the value of result

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

  • 0
    S

    Minor Change
    you could remove the if(i == 0) check, and do
    result = queue.peek().val before the for loop. It would save a lot of if checks


  • 0

    @szk258 yup, that makes sense.


  • 0
    R

    Python version:

    class Solution(object):
        def findBottomLeftValue(self, root):
            q = collections.deque()
            res = None
            q.appendleft(root)
            
            while q:
                sz = len(q)
                for i in xrange(0, sz):
                    node = q.popleft()
                    if i == 0:
                        res = node.val
                    if node.left:
                        q.append(node.left)
                    if node.right:
                        q.append(node.right)
            return res
    

    Javascript version:

    var findBottomLeftValue = function(root) {
        var result = 0;
            var queue = []
            queue.push(root);
            
            while(queue.length > 0) {
                var size = queue.length;
                for(var i = 0; i < size; i++) {
                    var node = queue.shift()
                    if(i == 0) result = node.val;
                    if(node.left != null) queue.push(node.left);
                    if(node.right != null) queue.push(node.right);
                }
            }
            return result;
    };
    

    C++ version:

    class Solution {
    public:
        int findBottomLeftValue(TreeNode* root) {
            int result = 0;
            queue<TreeNode*> queuee;
            queuee.push(root);
            
            while(queuee.size()) {
                int size = queuee.size();
                for(int i = 0; i < size; i++) {
                    TreeNode* node = queuee.front(); queuee.pop();
                    if(i == 0) result = node->val;
                    if(node->left != NULL) queuee.push(node->left);
                    if(node->right != NULL) queuee.push(node->right);
                }
            }
            return result;
        }
    };
    

    Golang:

    func findBottomLeftValue(root *TreeNode) int {
        result := 0
        q := make([]*TreeNode, 0)
        q = append(q, root)
        
        for len(q) > 0 {
            sz := len(q)
            for i:= 0; i < sz; i++ {
                node := q[0]
                q = q[1:]
                if i == 0 {
                    result = node.Val
                }
                if node.Left != nil {
                    q = append(q, node.Left)
                }
                if node.Right != nil {
                    q = append(q, node.Right)
                }
            }
        }
        return result
    }
    

  • 0
    Z

    @szk258 I tried this method and it brings me up to the 17ms (from 10), thx a lot.


  • 0

    Same idea here, but seems to be faster.

    public class Solution {
        public int findBottomLeftValue(TreeNode root) {
            Queue<TreeNode> q = new LinkedList<>();
            TreeNode leftMost = root;
            q.offer(root);
            while (!q.isEmpty()) {
                int qSize = q.size();
                leftMost = q.peek();
                while (qSize-- > 0) {
                    TreeNode curr = q.poll();
                    if (curr.left != null) q.offer(curr.left);
                    if (curr.right != null) q.offer(curr.right);
                }
            }
            return leftMost.val;
        }
    }
    

  • 0

    DFS (86%)

    public int findBottomLeftValue(TreeNode root) {
        int[] levelVal = new int[] {-1, -1};
        if(root != null) findBottom(root, 0, levelVal);
        return levelVal[1];
    }
    private void findBottom(TreeNode root, int level, int[] levelVal) {
        if(level > levelVal[0] && root.left == null && root.right == null) {
            levelVal[0] = level;
            levelVal[1] = root.val;
        }
        if(root.left != null) findBottom(root.left, level+1, levelVal);
        if(root.right != null) findBottom(root.right, level+1, levelVal);
    }

  • 0
    G

    DFS solution :

    class NodeAtDepth{
    int val = 0;
    int depth = 0;
    }
    public int findBottomLeftValue(TreeNode root) {
    NodeAtDepth nad = new NodeAtDepth();
    nad.val = root.val;
    getBottomLeftValue(root, 0, nad);
    return nad.val;
    }

    public void getBottomLeftValue(TreeNode node, int currentDepth,NodeAtDepth nad) {
        if(node == null) return;
        if (currentDepth > nad.depth) {
            nad.depth = currentDepth;
            nad.val = node.val;
        }
        getBottomLeftValue(node.left, currentDepth + 1, nad);
        getBottomLeftValue(node.right, currentDepth + 1, nad);
    }

  • 0

    Using a List to record first left node on each level, return the one for bottom level.

        public int findBottomLeftValue(TreeNode root) {
          List<Integer> levelLeft = new ArrayList();  
          int maxLevel = helper(levelLeft, root, 0);
          return levelLeft.get(maxLevel); 
        }
        
        int helper(List<Integer> levelLeft, TreeNode root, int level){
          if(root == null) return level - 1;
          if(levelLeft.size() == level) levelLeft.add(root.val);    
          int left = helper(levelLeft, root.left, level + 1); 
          int right = helper(levelLeft, root.right, level + 1);
          return Math.max(left, right);  
        }

Log in to reply
 

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