LeetCode 199. 二叉树的右视图

2020-04-23 00:00:00 视图 二叉树 leetcode

我的LeetCode:https://leetcode-cn.com/u/ituring/

我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii

LeetCode 199. 二叉树的右视图

题目

给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。

示例:

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-right-side-view
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

本题等价于树的层次遍历,只是结果要求记录每层的最右侧值;
层次遍历实为BFS,此外DFS也能解决;

思路1-BFS层次遍历

步骤:

  1. 每层从左至右入队;
  2. 顺次遍历队列节点的左右子节点并入队,且记录最后一个节点值至list;

算法复杂度:

  • 时间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
  • 空间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $

算法源码示例

package leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author ZhouJie
 * @date 2020年4月22日 下午9:12:49 
 * @Description: 199. 二叉树的右视图
 *
 */
public class LeetCode_0199 {

}

//  Definition for a binary tree node.
class TreeNode_0199 {
	int val;
	TreeNode_0199 left;
	TreeNode_0199 right;

	TreeNode_0199(int x) {
		val = x;
	}
}

class Solution_0199 {
	/**
	 * @author: ZhouJie
	 * @date: 2020年4月22日 下午10:11:22 
	 * @param: @param root
	 * @param: @return
	 * @return: List<Integer>
	 * @Description: 1-其实就是树的层次遍历,只是每层取了最右侧一个数
	 *
	 */
	public List<Integer> rightSideView(TreeNode_0199 root) {
		List<Integer> list = new ArrayList<Integer>();
		Deque<TreeNode_0199> deque = new ArrayDeque<>();
		if (root == null) {
			return list;
		}
		deque.offer(root);
		int val = root.val;
		while (!deque.isEmpty()) {
			int size = deque.size();
			while (size-- > 0) {
				TreeNode_0199 poll = deque.poll();
				if (poll.left != null) {
					deque.offer(poll.left);
				}
				if (poll.right != null) {
					deque.offer(poll.right);
				}
				val = poll.val;
			}
			list.add(val);
		}
		return list;
	}
}

    原文作者:图灵的图,图灵的灵。
    原文地址: https://www.cnblogs.com/izhoujie/p/12757359.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。

相关文章