Java solution by post-order traversal (beats 54%)


  • 2

    Since most of the answers use pre-order and level-order traversal. Here is my post-order traversal solution as an inspiration. The idea is to get the bottom left value of each subtree at each root, compare their depths and pass onto its parent.

    private class ResultSet {
        final int depth;
        final int val;
    
        ResultSet(int depth, int val) {
            this.depth = depth;
            this.val = val;
        }
    }
    
    public int findBottomLeftValue(TreeNode root) {
        return bottomLeft(root, 0).val;
    }
    
    private ResultSet bottomLeft(TreeNode root, int depth) {
        if (root == null) return null;
        if (root.left == null && root.right == null) return new ResultSet(depth, root.val);
        else if (root.left == null) return bottomLeft(root.right, depth + 1);
        else if (root.right == null) return bottomLeft(root.left, depth + 1);
        else {
            ResultSet left = bottomLeft(root.left, depth + 1);
            ResultSet right = bottomLeft(root.right, depth + 1);
            return right.depth > left.depth ? right : left;
        }
    }
    

  • 0
    O

    @swwl1992 I think, it is just DFS solution.And If you delete ResultSet and use a class attribute 'maxDepth' to save the value of max depth,the amount of your code will be reduced a lot, just like https://discuss.leetcode.com/topic/79877/dfs-java-solution


  • 0

    @ousness thanks for reading my code and thinking about it. However, the other solution mentioned by you is not the same as mine. Your solution utilises the property that in a preorder traversal, the sequence of visiting a tree is root -> left -> right. Therefore the right children which are on the same level as the left most one are blocked from updating the result.

    My solution tries to avoid a class attribute and I have been keeping it as a habit. A major advantage of my implementation is statelessness thus thread-safety.


Log in to reply
 

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