LeetCode-199 二叉树的右视图

Mr.He...

💬 描述

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

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

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

📋 代码1- DFS

按照根结点 -> 右子树 -> 左子树的顺序访问，就可以保证每层都是最先访问最右边的节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
     List<Integer> res = new ArrayList<>();
    
    public List<Integer> rightSideView(TreeNode root) {
        // 首次加入时，深度为0。
        dfs(root, 0);
        return res;
    }
    
    private void dfs(TreeNode node, int depth) {
        if (node == null) {
            return;
        }
        // 如果深度 == 结果集中的元素数。说明这是当前层的第一个元素。需要加到结果集中。否则不加。为什么呢？首先第一个进入dfs时，传入的深度为0，res长度也为0。这样可以把root加到res中。
        接着深度++，考察右孩子。此时深度又等于res元素数，会把右孩子加入res。继续往下... 
        若到某一层右孩子为null，会直接在上方返回，这样就会考虑左孩子。从而把左孩子加入集合。若左孩子也是null，会进行回溯，回溯到最近的、未考察过左孩子的节点，去考察它的左孩子（回溯时深度也会变小）。此时深度和res的长度是不相等的，这个左孩子不能加到res。就这样一路回溯。遇到合适的元素就会加到res。直到所有元素都考察一遍。
        // 这里把深度和结果集的元素数结合了起来，这个思路是以前没想到的- - 
        if (depth == res.size()) {
            res.add(node.val);
        }
        // 准备考察下层元素，深度+1。
        depth++;
        // 先考察右孩子。这样每次就能先判断右边的元素。
        dfs(node.right, depth);
        dfs(node.left, depth);
    }
}

复杂度：时间和空间均为O(n) 。

📋 代码2- BFS

对二叉树进行层次遍历，那么对于每层来说，最右边的结点一定是最后被遍历到的。二叉树的层次遍历可以用广度优先搜索实现。

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        int size = 0;
        
        while (!queue.isEmpty()) {
            // 获取当前queue的长度，这也 代表着二叉树当前层元素的数量。
            size = queue.size();
            // 遍历当前层的元素。为什么用普通for循环？
            // 因为这样可以知道是否到达了当前层的最后一个元素。
            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;
    }
}