网站技术解决方案的内容,电子商务网站规划,做的网站怎样适配手机屏幕,网站流量怎么变现呢题目
给定一棵二叉树的根节点 root #xff0c;请找出该二叉树中每一层的最大值。
示例1#xff1a;
输入: root [1,3,2,5,3,null,9]
输出: [1,3,9]
解释:1/ \3 2/ \ \ 5 3 9 示例2#xff1a;
输入: root [1,2,3]
输出: [1,3]
解释:1/ \2 3示例3#xff…题目
给定一棵二叉树的根节点 root 请找出该二叉树中每一层的最大值。
示例1
输入: root [1,3,2,5,3,null,9]
输出: [1,3,9]
解释:1/ \3 2/ \ \ 5 3 9 示例2
输入: root [1,2,3]
输出: [1,3]
解释:1/ \2 3示例3
输入: root [1]
输出: [1]示例4
输入: root [1,null,2]
输出: [1,2]
解释: 1 \2 示例5
输入: root []
输出: []提示
二叉树的节点个数的范围是 [0,104]-231 Node.val 231 - 1
注意本题与主站 515 题相同 力扣LeetCode官网 - 全球极客挚爱的技术成长平台
LCR 044. 在每个树行中找最大值 - 力扣LeetCode
题解
思路一DFS用先序遍历深搜并用 curHeight来标记遍历到的当前节点的高度。当遍历到 时判断是否更新该层节点的最大值。
代码
class Solution {public ListInteger largestValues(TreeNode root) {if (root null) return new ArrayListInteger();ListInteger res new ArrayListInteger();dfs(res, root, 0);return res;}public void dfs(ListInteger res, TreeNode root, int curHeight) {if (curHeight res.size()) //到新的一层加进来第一个值res.add(root.val);else res.set(curHeight, Math.max(res.get(curHeight), root.val));if (root.left ! null) dfs(res, root.left, curHeight 1);if (root.right ! null) dfs(res, root.right, curHeight 1);}
}
思路二BFS层序遍历一层一层扩展用 maxVal来标记该层节点的最大值。当前层处理完成之后maxVal即为当前层的最大值。
代码
class Solution {public ListInteger largestValues(TreeNode root) {if (root null) return new ArrayListInteger();ListInteger res new ArrayListInteger();QueueTreeNode queue new ArrayDequeTreeNode();queue.offer(root);while (!queue.isEmpty()) {int len queue.size();//当前len确保了len--到0时刚好处理完当前层int maxVal Integer.MIN_VALUE;while (len 0) {TreeNode t queue.poll();len--;maxVal Math.max(maxVal, t.val);if (t.left ! null) queue.offer(t.left);if (t.right ! null) queue.offer(t.right);}res.add(maxVal);}return res;}
}
tips关于值传递和引用传递。在Java中用的是值传递。在其它方法里面改变引用类型的值都是通过引用改变的当传递引用对象的时候传递的是复制的引用的对象句柄是复制过的也就是在内存中复制了一个句柄这两个句柄指向同一个对象所以改变这个句柄对应的空间的数据会影响到外部的变量虽然是复制的但是指向的是同一个地址当你把这个句柄指向其它对象的引用时并不会改变原来的值例如String因为用的是复制过的句柄。
