一、テーマ

力扣原题:https://leetcode-cn.com/problems/binary-tree-right-side-view/

二、BFS検索

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    public List rightSideView(TreeNode root) {
        if (null == root) {
            return new ArrayList<>();
        }

        List rightSideView = new ArrayList<>();
        List records = new ArrayList<>();
        records.add(root);
        while (!records.isEmpty()) {
            //         
            List childs = new ArrayList<>();
            for (TreeNode node : records) {
                if (null != node.left) {
                    childs.add(node.left);
                }
                if (null != node.right) {
                    childs.add(node.right);
                }
            }

            //              
            rightSideView.add(records.get(records.size() - 1).val);

            //   records  
            records = childs;
        }
        return rightSideView;
    }
}

基本構想:本題は二叉樹階層が遍歴する変種である.タイトルによると、ツリーの右ビューは、各層の最も右側のノードを保存すればよい.

時間複雑度:O(n).BFS検索では,ノードごとに1回アクセスする.

空間複雑度:O(n).最悪の場合、二叉木がチェーンテーブルに劣化した場合.

三、まとめ

肝心なのは,ツリー階層が遍歴する変種を連想し,BFS探索により解決することである.