Leetcode_Leetcode199二叉树的左视图,右视图
程序员文章站
2022-04-24 23:47:57
...
给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
示例:
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:1 <---
/ \
2 3 <---
\ \
5 4 <---
想法与思路:
1.因为右视图是同一层最右边的节点
1.构建Map Key 层高 , Value 节点值
2.想象中序遍历,右边的节点最后遍历到,map.put 相同key 覆盖,所以留在最后的一定就是同层最右边节点
3.树不会太深,不知道深度,尝试从0层遍历到最大层 ,取出 map的 value
代码
package com.offer.test.leetcode;
import java.util.*;
/**
* Created by szh on 2020/6/8.
*/
public class Leetcode_199_TreeRightView {
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public List<Integer> rightSideView(TreeNode root) {
List<Integer> list = new ArrayList<>();
Map<Integer,Integer> map = new HashMap<>();
map.values();
if(root != null){
traverse(root, 0, map);
}
int i = 0;
boolean flag = true;
while(flag){
if(map.containsKey(i)){
list.add(map.get(i));
++i;
}else{
flag = false;
}
}
return list;
}
public void traverse(TreeNode curRoot, int deep, Map<Integer,Integer> map){
map.put(deep,curRoot.val);
if(curRoot.left != null){
traverse(curRoot.left, deep + 1, map);
}
if(curRoot.right != null){
traverse(curRoot.right, deep + 1, map);
}
}
}
上一篇: Python是什么