网站建站所用的技术,营销型旅游网站建设,解析网站接口怎么做,wordpress网站上传给定一个二叉树的 根节点 root#xff0c;想象自己站在它的右侧#xff0c;按照从顶部到底部的顺序#xff0c;返回从右侧所能看到的节点值。 示例 1: 输入: [1,2,3,null,5,null,4]
输出: [1,3,4]示例 2:
输入: [1,null,3]
输出: [1,3]示例 3:
输入: []
输出: []解法一
题…给定一个二叉树的 根节点 root想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。 示例 1: 输入: [1,2,3,null,5,null,4]
输出: [1,3,4]示例 2:
输入: [1,null,3]
输出: [1,3]示例 3:
输入: []
输出: []解法一
题目意思再说的直白一些就是依次输出二叉树每层最右边的元素。
每层最右边可以想到二叉树的层次遍历我们只需要保存每层遍历的最后一个元素即可。
二叉树的层次遍历在 102 题 已经做过了代码拿过来用就可以。
我们只需要用一个队列每次保存下层的元素即可。
public ListInteger rightSideView(TreeNode root) {QueueTreeNode queue new LinkedListTreeNode();ListInteger res new LinkedList();if (root null)return res;queue.offer(root);while (!queue.isEmpty()) {int levelNum queue.size(); // 当前层元素的个数for (int i 0; i levelNum; i) {TreeNode curNode queue.poll();//只保存当前层的最后一个元素if (i levelNum - 1) {res.add(curNode.val);}if (curNode.left ! null) {queue.offer(curNode.left);}if (curNode.right ! null) {queue.offer(curNode.right);}}}return res;
}解法二
解法一的层次遍历是最直接的想法。我们也可以用深度优先遍历在 这里) 看到的。
二叉树的深度优先遍历在之前也讨论过了 94 题 的中序遍历、 144 题 的先序遍历以及 145 题 的后序遍历。
这里采用最简单的递归写法并且优先从右子树开始遍历。
用一个变量记录当前层数每次保存第一次到达该层的元素。
public ListInteger rightSideView(TreeNode root) {ListInteger res new LinkedList();rightSideViewHelper(root, 0, res);return res;
}private void rightSideViewHelper(TreeNode root, int level, ListInteger res) {if (root null) {return;}//res.size() 的值理解成当前在等待的层级数//res.size() 0, 在等待 level 0 的第一个数//res.size() 1, 在等待 level 1 的第一个数//res.size() 2, 在等待 level 2 的第一个数if (level res.size()) {res.add(root.val);}rightSideViewHelper(root.right, level 1, res);rightSideViewHelper(root.left, level 1, res);
}
