【Check 53】2024-04-16 - 199. 二叉树的右视图

[larscheng]

199. 二叉树的右视图

[larscheng]

思路

• 递归bfs：递归传递深度，每个深度都会对应一个待选元素，按照先序/中序遍历，收集每个深度对应的最右侧值
• 迭代bfs：层序遍历，收集每层最右侧元素

  代码

class Solution { //递归dfs public List rightSideView(TreeNode root) { List res = new ArrayList<>(); if (root==null){ return res; } helper(root,res,0); return res; }

private void helper(TreeNode root, List<Integer> res, int depth) {
    if (root==null){
        return;
    }
    if (res.size()<=depth){
        res.add(root.val);
    }else {
        res.set(depth,root.val);
    }

    helper(root.left, res, depth + 1);
    helper(root.right, res, depth + 1);
}

}

```java
    class Solution1 {

        public List<Integer> rightSideView(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            if (root==null){
                return res;
            }
            Deque<TreeNode> queue = new ArrayDeque<>();
            queue.add(root);
            while (!queue.isEmpty()){
                int size = queue.size();
                for (int i = 0; i < size ; i++) {
                    TreeNode node = queue.poll();
                    //队列先进先出，收集最后出来的
                    if (node.left!=null){
                        queue.add(node.left);
                    }
                    if (node.right!=null){
                        queue.add(node.right);
                    }
                    if (i==size-1){
                        res.add(node.val);
                    }
                }
            }
            return res;
        }
    }

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)