Problem
Given the root of a binary tree, return the leftmost value in the last row of the tree.
Example 1:
Input: root = [2,1,3] Output: 1 Example 2:
Input: root = [1,2,3,4,null,5,6,null,null,7] Output: 7 Constraints:
The number of nodes in the tree is in the range
[1, 104].-231 <= Node.val <= 231 - 1
Solution
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number} */ var findBottomLeftValue = function(root) { return dfs(root, 0)[0]; }; var dfs = function(node, depth) { var left = node.left ? dfs(node.left, depth + 1) : [node.val, depth]; var right = node.right ? dfs(node.right, depth + 1) : [node.val, depth]; return right[1] > left[1] ? right : left; }; Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(1).