我的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;
	}
}