当前位置：首页 > news >正文

199. Binary Tree Right Side View

news 来源：原创 2024/9/21 15:32:50

题目：

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

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

You should return [1, 3, 4].

链接： http://leetcode.com/problems/binary-tree-right-side-view/

题解：

求二叉树right side view。我们可以使用层序遍历，每次当前level == 0时，这个节点为此层最右边的节点，这时候我们把这个节点的value加入到结果集去。应该还有很多更好的方法，二刷要再细致一些。

Time Complexity - O(n)， Space Compleixty - O(n)。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null)
            return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int curLevel = 1, nextLevel = 0;
        
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            curLevel--;
            if(node.left != null) {
                queue.offer(node.left);
                nextLevel++;
            }
            if(node.right != null) {
                queue.offer(node.right);
                nextLevel++;
            }
            if(curLevel == 0) {
                curLevel = nextLevel;
                nextLevel = 0;
                res.add(node.val);
            }
        }
        
        return res;
    }
}

二刷:

依然是使用level order traversal，每次当curLevel = 0的时候，我们把当前node.val加入到结果集中。

也可以使用其他方法。下一次要补上recursive的。

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int curLevel = 1, nextLevel = 0;
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            curLevel--;
            if (node.left != null) {
                q.offer(node.left);
                nextLevel++;
            }
            if (node.right != null) {
                q.offer(node.right);
                nextLevel++;
            }
            if (curLevel == 0) {
                curLevel = nextLevel;
                nextLevel = 0;
                res.add(node.val);
            }
        }
        return res;
    }
}

三刷:

Java:

Recursive:

主要是使用一个int变量depth来控制递归。在当前深度等于list.size()时，我们加入root节点的值。因为每个level只取一个最右节点，所以我们先递归求解右子树，再求解左子树。

Time Complexity - O(n)， Space Compleixty - O(n)。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        rightSideView(res, root, 0);
        return res;
    }
    
    private void rightSideView(List<Integer> res, TreeNode root, int depth) {
        if (root == null) return;
        if (depth == res.size()) res.add(root.val);
        rightSideView(res, root.right, depth + 1);
        rightSideView(res, root.left, depth + 1);
    }
}