Inorder Traversal Solution, simple and beats 98.0%


  • 0
    M

    Keep record of heights, maximum height and res during traversal.
    Inorder traversal, since we are finding the leftmost element, so after we push all nodes of left boundary, compare the tree height and max height to decide if we need to update result. When finished a subtree traversal, decrease curHeight by 1, it means we have finished current level, go back to last level.

    public class Solution {

    private int curHeight = 0;
    private int maxHeight = 0;
    private int res = 0;
    public int findBottomLeftValue(TreeNode root) {
        inorder(root);
        return res;
    }
    public void inorder (TreeNode root) {
        if (root == null) return;
        // For each traversal, increase curHeight by 1
        curHeight++;
        inorder(root.left);
        // Left subtree traversal done, if height > maxHeight, update result
        if (curHeight > maxHeight) {
            maxHeight = curHeight;
            res = root.val;
        }
        inorder(root.right);
        // Finish current root left/right subtree, return to one level above
        curHeight -= 1;
    }
    

    }


Log in to reply
 

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