- 浏览: 173101 次
- 性别:
- 来自: 济南
文章分类
最新评论
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
For example:
Given the following binary tree,
1 <---
/ \
2 3 <---
\ \
5 4 <---
You should return [1, 3, 4].
给定一颗二叉树,输出它的right view,所谓right view就是从右边观察这棵树所能看到的节点。很容易想到的是用广搜,记录每一层最后一个节点。另外我们还可以用深度优先搜索,从树的右子树开始遍历,不过要维护一个变量layer,来判定当前节点是否应该能看到,因为如果右子树为空后,我们要观察左子树,因为左子树的深度可能比右子树大,我们在观察左子树时,通过layer与已经记录的右子树的节点比较,如果layer大于已经记录的节点数,那么这个节点就可以被观察到,如果小于或等于就不能被观察到。下面给出两种方法的代码:
1,广度优先搜索
2,深度优先搜索
For example:
Given the following binary tree,
1 <---
/ \
2 3 <---
\ \
5 4 <---
You should return [1, 3, 4].
给定一颗二叉树,输出它的right view,所谓right view就是从右边观察这棵树所能看到的节点。很容易想到的是用广搜,记录每一层最后一个节点。另外我们还可以用深度优先搜索,从树的右子树开始遍历,不过要维护一个变量layer,来判定当前节点是否应该能看到,因为如果右子树为空后,我们要观察左子树,因为左子树的深度可能比右子树大,我们在观察左子树时,通过layer与已经记录的右子树的节点比较,如果layer大于已经记录的节点数,那么这个节点就可以被观察到,如果小于或等于就不能被观察到。下面给出两种方法的代码:
1,广度优先搜索
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<Integer> rightSideView(TreeNode root) { List<Integer> list = new ArrayList<Integer>(); Queue<TreeNode> queue = new LinkedList<TreeNode>(); if(root == null) return list; queue.offer(root); int count = 1; int helper = 0; while(!queue.isEmpty()) { TreeNode node = queue.poll(); count --; if(node.left != null) { queue.offer(node.left); helper ++; } if(node.right != null) { queue.offer(node.right); helper ++; } if(count == 0) { list.add(node.val); count = helper; helper = 0; } } return list; } }
2,深度优先搜索
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<Integer> rightSideView(TreeNode root) { List<Integer> list = new ArrayList<Integer>(); if(root == null) return list; getView(root, list, 1); return list; } public void getView(TreeNode root, List<Integer> list, int layer) { if(root == null) return; if(layer > list.size()) list.add(root.val); getView(root.right, list, layer + 1); getView(root.left, list, layer + 1); } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 224Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 222You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 339Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 330Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 448Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 508Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 427Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 425The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 383Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 514Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 528Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 366All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 858Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 879Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 552Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 598Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 761Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 731You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 626For a undirected graph with tre ...
相关推荐
Binary Tree Right Side View Invert Binary Tree Binary Search Tree Iterator Binary Tree Zigzag Level Order Traversal Recover Binary Search Tree Same Tree Symmetric Tree Balanced Binary Tree Flatten ...
102-Binary Tree Level Order Traversal199-Binary Tree Right Side View:层次遍历的一个运用树的构造给出前中后序的序列中的两个,构造一棵树。递归。前序 parent left-child right-child中序 left-child parent ...
leetcode做过的LeetCode的题目记录一下。对一些比较经典的题型进行分类总结。... Binary Tree Right Side View【2020-01-15】130. Surrounded Regions【2020-01-09】114. Flatten Binary Tree to Linked List
leetcode中文版 我会尽力将LeetCode上所有的题目都用动画的形式演示出来,计划用3到4年时间去完成它,期待与你见证这一天! 文章最新首发于微信公众号 ...Right Side View 203 移除链表元素 206 反转
题目链接: https://leetcode-cn.com/problems/binary-tree-right-side-view/ 解题思路: 树的层序遍历,先放左节点,再放右节点 每次将一层都放完的时候,将最后一个放入的元素加入到结果集中,其余直接清空 然后...
"binary-tree-right-side-view"; String answerPath = "leetcode.mid.BinaryTreeRightSideView"; 「剑指Offer」 通过手动输入题目信息生成数据信息,类似LeetCode自动更新Readme.md中的题解表格 使用方式 在 Sword2...
Theoretically a b+tree is O(N log k N) or log base k of N, now for the typical values of k which are above 200 for example the b+tree should outperform any binary tree because it will use less ...
on left and right side of a text box.<END><br>40,Assist.zip A simple application with source code which shows how to save the contents of a rich text box without the help of common dialog box.<END>...
Updated module: ElementTree 1.3 Build and C API Changes Capsules Port-Specific Changes: Windows Port-Specific Changes: Mac OS X Port-Specific Changes: FreeBSD Other Changes and Fixes Porting to ...
Server Side ViewState 在服务器端存贮ViewState (ASP.NET 2.0) VS2005 ASP.NET本地化学习笔记&感受 在自定义Server Control中捆绑JS文件 Step by Step 深度解析Asp.Net2.0中的Callback机制 使用 Web 标准生成 ASP...