Java-LeetCode199. 二叉树的右视图-层次遍历 | 递归

• 算法
  • 1.层次遍历
  • 2.每层遍历取最后一个节点即是右视图可以看到的节点

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

    Deque<TreeNode> deque = new LinkedList<TreeNode>();
    deque.offer(root);
    while (!deque.isEmpty()) {
        int size = deque.size();
        list.add(deque.peekLast().val);
        for (int i = 0; i < size; i++) {
            TreeNode curr = deque.poll();
            if (curr.left != null) {
                deque.offer(curr.left);
            }
            if (curr.right != null) {
                deque.offer(curr.right);
            }
        }
    }
    return list;
}

• 算法
  • 1.递归，每层只保存一个最右侧的节点
    • 1.1当深度和结果中节点个数相等时，说明这层的右视图节点是这个节点；否则，说明它的右侧兄弟节点已经添加过这层的右视图节点
    • 1.2接着依次递归右子树和左子树

public List<Integer> rightSideView(TreeNode root) {
    ArrayList<Integer> list = new ArrayList<Integer>(10);
    rightSideView(root, list, 0);
    return list;
}

private void rightSideView(TreeNode root, ArrayList<Integer> list, int depth) {
    if (root == null) {
        return;
    }

    if (depth == list.size()) {
        list.add(root.val);
    }
    rightSideView(root.right, list, depth+1);
    rightSideView(root.left, list, depth+1);
}