Simple Java Solution, beats 100.0%!


  • 33
    C
    public class Solution {
        int ans=0, h=0;
        public int findBottomLeftValue(TreeNode root) {
            findBottomLeftValue(root, 1);
            return ans;
        }
        public void findBottomLeftValue(TreeNode root, int depth) {
            if (h<depth) {ans=root.val;h=depth;}
            if (root.left!=null) findBottomLeftValue(root.left, depth+1);
            if (root.right!=null) findBottomLeftValue(root.right, depth+1);
        }
    }
    

    No global variables, 6ms (faster):

    public class Solution {
        public int findBottomLeftValue(TreeNode root) {
            return findBottomLeftValue(root, 1, new int[]{0,0});
        }
        public int findBottomLeftValue(TreeNode root, int depth, int[] res) {
            if (res[1]<depth) {res[0]=root.val;res[1]=depth;}
            if (root.left!=null) findBottomLeftValue(root.left, depth+1, res);
            if (root.right!=null) findBottomLeftValue(root.right, depth+1, res);
            return res[0];
        }
    }
    

  • 2
    L

    Easy-understanding!


  • 2
    I

    Add if (null != root.left) and if (null != root.right) before findLeftMostNode(root.left, depth+1);findLeftMostNode(root.right, depth+1); could improve efficiency of recursion.


  • 0
    C

    @IcareWang Thanks! Modified.


  • 0
    S

    @ckcz123 I assume this fails if there is right node at more depth -makes sense?


  • 0
    C

    @saisaripalli We will find the first node in the deepest level, no matter whether it's a left node or right node.


  • 1
    S

    @ckcz123 Hi, thank you for your response. "find the leftmost value in the last row of the tree" -I was under impression that in the question they only want leftmost node value if it has or just print leftmost node in whatever row of greater depth-Yes? I was confused -correct me.


  • 1
    C

    @saisaripalli Find the last row, and find the leftmost value of this row.


  • 0
    H
    This post is deleted!

  • 0
    T

    @IcareWang Would you please advise why it could improve efficiency? thx


  • 1
    M

    Similar idea, no global variable, with some comments:

        private void helper(TreeNode root, int row, int[] result/*result-val, lowest row*/ ){
            if(root==null)
                return;
            
            if(row > result[1]){
                result[0] = root.val;
                result[1] = row;
            }
            
            helper(root.left, row+1, result); //no need to care about the cols of a row, as here we always go to left first, the left-most node of a row will always be captured first 
            helper(root.right, row+1, result);
        }
        
        public int findBottomLeftValue(TreeNode root) {
            if(root==null)
                return 0;
            int[] result = {root.val, 0};
            helper(root, 0, result);
            return result[0];
        }
    

  • 0
    A

    @tobelzm I'm not sure efficiency is the right word, but without those lines there is a chance of NullPointerException. Because if you pass a null node to the function at a greater depth, root.val will cause the exception. Null nodes will be encountered when you reach a leaf or a node with only one branch.


  • 0

    @mycoy Got something similar:

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

  • 1
    Y

    I had a pretty much same dfs solution. I feel for this problem, using dfs is preferable as it takes less memory compare to bfs. (not considering the stack space used for recursion...)

    public class Solution {
        int maxDepth = 0;
        int val = 0;
    
        private void dfs(TreeNode root, int depth) {
            if (root != null) {
                if (depth > maxDepth) {
                    val = root.val;
                    maxDepth = depth;
                }
                dfs(root.left, depth + 1);
                dfs(root.right, depth + 1);
            }
        }
    
        public int findBottomLeftValue(TreeNode root) {
            dfs(root, 1);
            return val;
        }
    }
    

  • 0

    I noticed that you are all using a int [] res to store the maxDepth and the result´╝îis it because the res array always has the same memory address when going to the next recursion level?


  • 0
    C

  • 0
    R

    @ckcz123
    We got the same solution. This does not use extra space as the other solution using Queue do.


Log in to reply
 

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