欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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);
        }
    }


}

 

Leetcode_Leetcode199二叉树的左视图,右视图

 

相关标签: Leetcode