Leetcode - 199. 二叉树的右视图

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

    // 可以进行前序遍历，每读取到一个节点（假设层数为layer），就将rightView[layer]的值更新为该节点的val值
    // 由于前序遍历时，同一层节点中，最右的节点总是最后被发现，因此遍历结束后rightView就存储了各层的最右节点的值
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> rightView = new ArrayList<>();
        search(root, rightView, 0);
        return rightView;
    }

    // 对二叉树node进行前序遍历，layer表示node节点所在的层数
    private void search(TreeNode node, List<Integer> rightView, int layer){
        
        // 忽略空节点
        if (node == null) {
            return;
        }
        
        // 将rightView扩容到layer
        while (layer >= rightView.size()) {
            rightView.add(null);
        }
        
        // 将该节点的val值存放到rightView[layer]中
        rightView.set(layer, node.val);
        
        // 继续搜索左右子树
        search(node.left, rightView, ++layer);
        search(node.right, rightView, layer);
    }
}