Problem
Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).
Example 1:
Input: root = [1,3,2,5,3,null,9] Output: [1,3,9] Example 2:
Input: root = [1,2,3] Output: [1,3] Constraints:
The number of nodes in the tree will be in the range
[0, 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 largestValues = function(root) { var res = []; dfs(root, 0, res); return res; }; var dfs = function(root, row, res) { if (!root) return; res[row] = Math.max( res[row] === undefined ? Number.MIN_SAFE_INTEGER : res[row], root.val, ); dfs(root.left, row + 1, res); dfs(root.right, row + 1, res); }; Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).