199、二叉树的左视图
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例:
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <---
/ \
2 3 <---
\ \
5 4 <---
链接：https://leetcode-cn.com/problems/binary-tree-right-side-view
题解
1、层序遍历——宽度优先搜索
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
class Node{
TreeNode node;
int level;
public Node(TreeNode node,int level){
this.node = node;
this.level = level;
}
}
public List<Integer> rightSideView(TreeNode root) {
if (root == null) {
return new ArrayList<Integer>();
}
// 层序遍历
Queue<Node> queue = new LinkedList<>();
queue.offer(new Node(root,1));
List<Integer> res = new ArrayList<>();
while(!queue.isEmpty()) {
// 只有在最后一层的最后一个节点才会有效 或者一层只有一个节点。
if(queue.size() == 1){
res.add(queue.peek().node.val);
}
Node node = queue.peek();
queue.poll();
// 如果是下一层节点，
if (queue.peek() != null && queue.peek().level == node.level+1){
res.add(node.node.val);
// 打印下一层
// print(queue);
}
if (node.node.left != null){
queue.offer(new Node(node.node.left,node.level+1));
}
if (node.node.right != null){
queue.offer(new Node(node.node.right,node.level+1));
}
}
return res;
}
private void print(Queue<Node> queue) {
String str = "[";
for (Node node : queue){
str += node.node.val + ",";
}
str = str.substring(0,str.length() - 1);
str+= "]";
System.out.println(str);
}
}
// 官方实现
class Solution {
public List<Integer> rightSideView(TreeNode root) {
// 结果hash表，对于同一深度值存储从左往右遍历的最后一个节点
Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();
int max_depth = -1;
Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
Queue<Integer> depthQueue = new LinkedList<Integer>();
nodeQueue.add(root);
depthQueue.add(0);
while (!nodeQueue.isEmpty()) {
TreeNode node = nodeQueue.remove();
int depth = depthQueue.remove();
if (node != null) {
// 维护二叉树的最大深度
max_depth = Math.max(max_depth, depth);
// 由于每一层最后一个访问到的节点才是我们要的答案，因此不断更新对应深度的信息即可
rightmostValueAtDepth.put(depth, node.val);
nodeQueue.add(node.left);
nodeQueue.add(node.right);
depthQueue.add(depth+1);
depthQueue.add(depth+1);
}
}
List<Integer> rightView = new ArrayList<Integer>();
for (int depth = 0; depth <= max_depth; depth++) {
rightView.add(rightmostValueAtDepth.get(depth));
}
return rightView;
}
}
// 链接：https://leetcode-cn.com/problems/binary-tree-right-side-view/solution/er-cha-shu-de-you-shi-tu-by-leetcode-solution/
// 简化版实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> rightSideView(TreeNode root) {
//保存结果
List<Integer> res = new LinkedList<>();
//保存节点
if(root == null)
return res;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
// 获取该层的节点数量
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode tmp = q.poll();
// 将下一层节点加入队列
if(tmp.left != null)
q.add(tmp.left);
if(tmp.right != null)
q.add(tmp.right);
// 特殊处理最后一个元素，简单直接
if(i == size - 1)
res.add(tmp.val);
}
}
return res;
}
}
2、根-右-左——深度优先搜索
class Solution {
public List<Integer> rightSideView(TreeNode root) {
Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();
int max_depth = -1;
// 节点栈
Stack<TreeNode> nodeStack = new Stack<TreeNode>();
// 深度栈
Stack<Integer> depthStack = new Stack<Integer>();
nodeStack.push(root);
depthStack.push(0);
while (!nodeStack.isEmpty()) {
TreeNode node = nodeStack.pop();
int depth = depthStack.pop();
if (node != null) {
// 维护二叉树的最大深度
max_depth = Math.max(max_depth, depth);
// 如果不存在对应深度的节点我们才插入
// 栈先进后出，每一层的最后一个节点
if (!rightmostValueAtDepth.containsKey(depth)) {
rightmostValueAtDepth.put(depth, node.val);
}
nodeStack.push(node.left);
nodeStack.push(node.right);
depthStack.push(depth+1);
depthStack.push(depth+1);
}
}
List<Integer> rightView = new ArrayList<Integer>();
for (int depth = 0; depth <= max_depth; depth++) {
rightView.add(rightmostValueAtDepth.get(depth));
}
return rightView;
}
}
// 链接：https://leetcode-cn.com/problems/binary-tree-right-side-view/solution/er-cha-shu-de-you-shi-tu-by-leetcode-solution/
// 简化版实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<Integer> res = new LinkedList<>();
int depth = 0;
public List<Integer> rightSideView(TreeNode root) {
helper(root, 0);
return res;
}
private void helper(TreeNode root, int curDepth) {
if (root == null) {
return;
}
// 当前节点是下一层的最右节点
if (curDepth == depth) {
// 加入到结果中
res.add(root.val);
// 一旦找到该层的最右节点，就更新下一层，之后同一层的节点不会通过
depth++;
}
// 先找右节点，如果右节点存在的话，那么下一层的能看到的数据就是右节点
helper(root.right, curDepth+1);
// 相同的curDepth作为参数，如果右节点存在，那么左节点的数据不可能存入res
helper(root.left, curDepth+1);
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
