【二叉树专题】额外补充：199. 二叉树的右视图-跟着帅地玩副业，开拓第二曲线PlayOffer

宁永久会员 2023年3月15日下午4:19

层序遍历取最后一个元素

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }
        //层序遍历的思路
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        queue.offer(root);
        while(queue.size() > 0){
            int k = queue.size();
            for(int i = 0; i < k; i ++){
                TreeNode node = queue.poll();
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
                if(i == k - 1){
                    list.add(node.val);
                }
            }
        }
        return list;
    }
}

0 赞同 0 条回复

lucca 普通 2023年1月7日下午3:34

层序遍历，取每层最后一个

时间复杂度 O(N)
空间复杂度 O(N)

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new LinkedList<>();
        if (root == null) return ans;

        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            Queue<TreeNode> t = new LinkedList<>();
            int val = q.peek().val;
            while (!q.isEmpty()) {
                TreeNode node = q.poll();
                val = node.val;
                if (node.left != null) t.add(node.left);
                if (node.right != null) t.add(node.right);
            }
            q = t;
            ans.add(val);
        }
        return ans;
    }
}

0 赞同 0 条回复

cute. 普通 2023年1月5日下午10:39

// 层序遍历
// 遍历到每层最后一个节点时加入res中
var rightSideView = function(root) {
  if(!root)
    return [];
  let queue = [root]; // 把根元素加入队列
  let res = []; // 用来存储每层最后一个元素值
  while(queue.length) {
      let n = queue.length;
      for(let i = 0; i < n; i++) {
          let node =  queue.shift(); // 取出队列第一个元素
          if(i === n - 1) res.push(node.val); // 当前一层的最后一个元素时，把值加入到res中
          node.left && queue.push(node.left);
          node.right && queue.push(node.right);
      }
  }
  return res;
};

时间复杂度:O(n)
空间复杂度:O(n)

0 赞同 0 条回复

🚲南下普通 2022年11月30日下午8:23

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        queue<TreeNode*> que;//使用层序遍历方式
        if(root!=nullptr) que.push(root);
        while(!que.empty()){
            int size = que.size();
            for(int i = 0; i< size; i++){
                TreeNode* node = que.front();
                que.pop();
                if(i==size-1) result.push_back(node->val);//第size-1个
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return result;

    }
};

0 赞同 0 条回复

symbol 普通 2022年11月27日上午11:33

func rightSideView(root *TreeNode) []int {
    stack := []*TreeNode{} // 定义一个存树节点的队列
    res := []int{}
    if root == nil{ //特殊情况·
        return res
    }
    stack = append(stack, root) //第一次把根节点放入队列中
    for len(stack) > 0{//队列不空就一直执行 这里相当于while
        length := len(stack) //每一层节点个数
        res = append(res,stack[length-1].Val) //每一层的最右节点存入答案集
        for i := 0;i < length;i++{ //遍历每一层的每一个节点
            node := stack[0] // 弹出队首元素
            stack = stack[1:] // 更新队列元素
            if node.Left != nil{// 左孩子如队列
                stack = append(stack, node.Left)
            }
            if node.Right != nil{ //右孩子入队列
                stack = append(stack, node.Right)
            }
        }
    }
    return res
}

0 赞同 0 条回复

xye 普通 2022年11月19日下午9:50

var res []int
func rightSideView(root *TreeNode) []int {
    res = []int{}
    dfs(root, 0)
    return res
}

func dfs(root *TreeNode, depth int) {
    //当root为空，终止执行
    if root == nil {
        return
    }
    //当深度=数组长度，说明这个层的最右节点还没加进去，执行加入操作
    if depth == len(res) {
        res = append(res, root.Val)
    }
    depth = depth + 1
    //先右再左，递归调用
    dfs(root.Right, depth)
    dfs(root.Left, depth)
}

时间O(n)空间O(n)

0 赞同 0 条回复

刺猬普通 2022年11月16日下午5:04

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> v;
        if(root == nullptr) return v;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            v.push_back(q.back()->val);
            int size = q.size();
            while(size--) {
                TreeNode* node = q.front();
                q.pop();
                if(node->left)
                    q.push(node->left);
                if(node->right)
                    q.push(node->right);
            }
        }
        return v;
    }
};

时间复杂度：O（n）
空间复杂度：O（n）

0 赞同 0 条回复

浅夏的无奈普通 2022年11月13日下午5:50

时间复杂度：O（n）
空间复杂度：O（n）

class Solution {
    List<Integer> res = new ArrayList<>();

    public List<Integer> rightSideView(TreeNode root) {
        dfs(root, 0); // 从根节点开始访问，根节点深度是0
        return res;
    }

    private void dfs(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        // 先访问 当前节点，再递归地访问 右子树 和 左子树。
        if (depth == res.size()) {   // 如果当前节点所在深度还没有出现在res里，说明在该深度下当前节点是第一个被访问的节点，因此将当前节点加入res中。
            res.add(root.val);
        }
        depth++;
        dfs(root.right, depth);
        dfs(root.left, depth);
    }
}

0 赞同 0 条回复

yanshuojune 普通 2022年11月13日下午3:32

思路：使用广度优先搜索方法，将每一层的最后一个节点值放入结果列表。
时间复杂度：O（n）
空间复杂度：O（n）

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        # 广度优先搜索
        import collections
        queue, res = collections.deque(), []
        queue.append(root)
        if not root:
            return []
        while queue:
            length = len(queue)
            for i in range(length):
                node = queue.popleft()
                # 添加子节点入队列
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            # 当前层的最后一个节点值添加到结果列表
            res.append(node.val)
        return res

0 赞同 0 条回复

黎昕普通 2022年11月11日下午8:39

和前面一道题：层序遍历，返回一个二维列表一样的思路
时间空间 O(n)

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        # 实际上应该是求层序遍历中每层的最后一个节点的问题
        if not root:
            return []
        queue1=collections.deque()
        queue2=collections.deque()
        ans=[]
        queue1.append(root)
        while queue1:
            node=queue1.popleft()
            if node.left:
                queue2.append(node.left)
            if node.right:
                queue2.append(node.right)
            if not queue1:
                ans.append(node.val)
                queue1,queue2=queue2,queue1
        return ans

0 赞同 0 条回复

小肸永久会员 2022年11月11日下午5:35

实现方式一：层次遍历+BFS。取每一层的最后一个节点加入到结果集。因为每一个节点都需要访问一次，所以时间复杂度为O(N)，需要用到一个队列，空间复杂度为O(N)。

class Solution {
    private List<Integer> res = new LinkedList<>();
    public List<Integer> rightSideView(TreeNode root) {
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int count = queue.size();
            for (int i = 0; i < count; i ++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
                if (i == count - 1) {
                    res.add(node.val);
                }
            }
        }
        return res;
    }
}

实现方式二：DFS。按先访问右节点，再访问左节点的顺序，只需取开始访问这一层的第一个节点加入到结果集中。时间和空间复杂度都为O(N)。

class Solution {
    private List<Integer> res = new LinkedList<>();
    private int height = 0;
    public List<Integer> rightSideView(TreeNode root) {
        dfs(root, 0);
        return res;
    }
    private void dfs(TreeNode root, int h) {
        if (root == null) {
            return;
        }
        if (height == h) {
            height ++;
            res.add(root.val);
        }
        if (root.right != null) {
            dfs(root.right, h + 1);
        }
        if (root.left != null) {
            dfs(root.left, h + 1);
        }
    }
}

0 赞同 0 条回复

波波_1936 普通 2022年11月10日下午11:30

    public List<Integer> rightSideView(TreeNode root) {
        //层序遍历
        //时间复杂度O(n)
        //空间复杂度O(n)
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {

            int len = queue.size();
            while (len > 0) {
                len--;

                TreeNode node = queue.poll();
                if (node != null) {
                    if (node.left != null) {
                        queue.add(node.left);
                    }
                    if (node.right != null) {
                        queue.add(node.right);
                    }
                }
                if (len == 0) {
                    if (node != null) {
                        res.add(node.val);
                    }
                }
            }
        }
        return res;
    }

0 赞同 0 条回复

lobort 普通 2022年11月10日下午2:26

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        //直接利用广度优先遍历/层次遍历
        //利用变量 size 来判断是否是该层最后（最右）一个元素
        //时间复杂度O(n) 空间复杂度O(n)
        ArrayList<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode cur = queue.poll();
                if(cur.left != null){
                    queue.offer(cur.left);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }
                if(i == size -1){
                    res.add(cur.val);
                }
            }
        }
        return res;
    }
}

0 赞同 0 条回复

@ 普通 2022年11月10日上午10:45

思路：哈希+DFS
时间复杂度：O(n)，其中n为二叉树的节点数
空间复杂度：O(n)

class Solution {
    List<Integer> res = new LinkedList<>();
    Map<Integer, Integer> map = new HashMap<>();

    public List<Integer> rightSideView(TreeNode root) {

        int i = 0;//用来表示树的当前层数

        find(root, i);
        res = new ArrayList(map.values());

        return res;

    }

    public void find(TreeNode root, int i) {
        if (root == null)
            return;

        //用来判断树的每一层的是否存放最右边的值了
        if (!map.containsKey(i))
            map.put(i, root.val);

        i++;

        find(root.right, i);
        find(root.left, i);

    }

}

0 赞同 0 条回复

酥合普通 2022年11月8日下午10:19

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
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);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                if (i == size - 1) {  //将当前层的最后一个节点放入结果列表
                    res.add(node.val);
                }
            }
        }
        return res;
    }
}

时间复杂度:O(n)
空间复杂度:O(n)

0 赞同 0 条回复

天然普通 2022年11月5日下午2:10

层次遍历时间复杂度O(n),空间复杂度O(n)

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root: return []
        num,res= [root],[]
        while num:
            res.append(num[-1].val)
            for _ in range(len(num)):
                tem = num.pop(0)
                if tem.left: num.append(tem.left)
                if tem.right:num.append(tem.right)

        return res

0 赞同 0 条回复

你有点可爱喔普通 2022年11月5日下午12:25

深度优先搜索；时间复杂度O(n),空间复杂度O(n)

class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        preorder(root,0);
        return res;
    }
    void preorder(TreeNode root,int depth){
        if (root == null){
            return ;
        }
        if(depth == res.size()){
            res.add(root.val);
        }
    depth++;
        preorder(root.right,depth);
        preorder(root.left,depth);
    }
}

0 赞同 0 条回复

just 普通 2022年11月5日上午10:51

//levelorder层序遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:

vector<int> rightSideView(TreeNode* root) {
    vector<int> res;
    if(!root) return res;
    queue<TreeNode*> que;
    que.push(root);
    while(!que.empty()){
        int size=que.size();
        for(int i=0;i<size;++i){
            TreeNode* cur=que.front();
            que.pop();
            if(i==size-1) res.push_back(cur->val);
            if(cur->left) que.push(cur->left);
            if(cur->right) que.push(cur->right);
        }
    }
    return res;

}

};

0 赞同 0 条回复

mpweixin用户永久会员 2022年11月4日下午9:15

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
       List<Integer> list = new ArrayList<>();
        if(root == null)  return list;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            for(int i=queue.size();i>0;i--){
                TreeNode q = queue.poll();
                if(q.left != null) queue.add(q.left);
                if(q.right != null) queue.add(q.right);  
                if(i == 1) list.add(q.val);  
            }
        }
    return list;
    }
}

int i=1时，意味着一层中最后一个元素，这么把他拿出去

0 赞同 0 条回复

派大星普通 2022年11月4日下午8:18

class Solution {
//使用分层遍历的方法提取每一层的元素，最后输出每层的最后一个数
    public List<Integer> rightSideView(TreeNode root) {
        if(root==null)return new ArrayList<>();
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        List<List<Integer>> nodes = new ArrayList<>();
        queue1.add(root);
        while (!queue1.isEmpty()||!queue2.isEmpty()){
            if(!queue1.isEmpty()){
                List<Integer> list = new ArrayList<>();
                while(!queue1.isEmpty()){
                    TreeNode node = queue1.poll();
                    list.add(node.val);
                    if (node.left != null) queue2.add(node.left);
                    if (node.right != null) queue2.add(node.right);
                }
                nodes.add(list);
            }else if(!queue2.isEmpty()){
                List<Integer> list = new ArrayList<>();
                while(!queue2.isEmpty()){
                    TreeNode node = queue2.poll();
                    list.add(node.val);
                    if (node.left != null) queue1.add(node.left);
                    if (node.right != null) queue1.add(node.right);
                }
                nodes.add(list);
            }
        }
        List<Integer> values = new ArrayList<>();
        for (List<Integer> node : nodes) {
            values.add(node.get(node.size()-1));
        }

        return values;
    }
}

0 赞同 0 条回复

青木普通 2022年11月4日下午5:56

/**
    就简单层序遍历

    时间复杂度O(n)
    空间复杂度O(n)
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();
        TreeNode node = new TreeNode();

        if(root==null) return ans;

        q1.offer(root);
        ans.add(root.val);
        while(!q1.isEmpty()){
            while(!q1.isEmpty()){
                node = q1.poll();
                if(node.left!=null) q2.offer(node.left);
                if(node.right!=null) q2.offer(node.right);
            }
            q1 = new LinkedList<>();

            if(q2.isEmpty()) return ans;
            while(!q2.isEmpty()){
                node = q2.poll();
                q1.offer(node);
            }
            ans.add(node.val);
            q2 = new LinkedList<>();
        }
        return ans;
    }
}

/**
    dfs递归写法

    时间复杂度O(n)
    空间复杂度O(n)
 */
class Solution {
    List<Integer> ans = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        dfs(root, 0);
        return ans;
    }

    public void dfs(TreeNode root, int depth) {
        if(root==null) return;

        if(depth == ans.size()){
            ans.add(root.val);
        }
        depth++;
        dfs(root.right, depth);
        dfs(root.left, depth);
    }
}

/**
    题解中的迭代dfs

    时间复杂度O(n)
    空间复杂度O(n)
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        Deque<TreeNode> ns = new ArrayDeque<>();
        Deque<Integer> ds = new ArrayDeque<>();
        int max_depth = -1;
        List<Integer> ans = new ArrayList<>();

        if(root==null) return ans;
        ns.push(root);
        ds.push(0);

        while(!ns.isEmpty()){
            TreeNode node = ns.pop();
            int depth = ds.pop();

            max_depth = Math.max(depth, max_depth);

            if(!map.containsKey(depth)){
                map.put(depth, node.val);
            }

            if(node.left != null){
                ns.push(node.left);
                ds.push(depth+1);
            }
            if(node.right != null){
                ns.push(node.right);
                ds.push(depth+1);
            }
        }

        for(int depth=0; depth<=max_depth; depth++){
            ans.add(map.get(depth));
        }
        return ans;
    }
}

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月4日下午5:15

时间空间复杂度都为O（lgn）

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

0 赞同 0 条回复

是梦终空永久会员 2022年11月4日下午2:27

层序遍历，两层while循环，入队再出队，size为0就结束内层循环.外层循环再更新size
时间O(n)
空间O(n)

class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        if(root == null)    return list;
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        TreeNode pre=null;
        while(!que.isEmpty()){
            int size = que.size();
            while(size>0){
                size--;
                pre = que.remove();
                if(pre.left!=null)
                    que.add(pre.left);
                if(pre.right!=null)
                    que.add(pre.right);
            }
            list.add(pre.val);
        }
        return list;
    }
}

0 赞同 0 条回复

追普通 2022年11月4日下午12:43

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        unordered_map<int, int> rightmostValueAtDepth;
        int max_depth = -1;

        queue<TreeNode*> nodeQueue;
        queue<int> depthQueue;
        nodeQueue.push(root);
        depthQueue.push(0);

        while(!nodeQueue.empty()){
            TreeNode* node = nodeQueue.front(); nodeQueue.pop();
            int depth = depthQueue.front(); depthQueue.pop();

        if(node != nullptr){

            //维护二叉树最大深度
            max_depth = max(max_depth, depth);

            //每一层最后一个访问的节点是我们要的答案，因此不断更新对应深度的信息即可
            rightmostValueAtDepth[depth] = node->val;
            nodeQueue.push(node->left);
            nodeQueue.push(node->right);
            depthQueue.push(depth + 1);
            depthQueue.push(depth + 1);
        }
        }

        vector<int> rightView;
        for(int depth = 0; depth <= max_depth; depth++) rightView.push_back(rightmostValueAtDepth[depth]);

        return rightView;
    }
};

使用层序遍历得到二叉树队列，同时建立一个深度队列对应节点队列，然后层序遍历每层最后一个节点放入到map中对应每一个深度的键，最后将map的值输出存储到数组中

0 赞同 0 条回复

易水寒永久会员 2022年11月4日上午11:23

层序遍历

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        if(root == null) {
            return res;
        }
        else {
            q.add(root);
        }
        while(!q.isEmpty()) {
            int len = q.size();
            for(int i = 0; i < len; i++) {
                TreeNode t = q.poll();
                if(i == len-1) {
                    res.add(t.val);
                }
                if(t.left != null) {
                    q.add(t.left);
                }
                if(t.right != null) {
                    q.add(t.right);
                }
            }
        }
        return res;
    }
}

0 赞同 0 条回复

T 普通 2022年11月4日上午8:09

用层序遍历解决

class Solution {

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            for(int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if(i == (size - 1)) list.add(node.val);
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
        }
        return list;
    }
}

0 赞同 0 条回复

y 普通 2022年11月3日下午10:58

//  层序遍历，遍历到每层最后一个节点时加入res中
var rightSideView = function(root) {
  if(!root) return [];
  let queue = [root];
  let res = [];
  while(queue.length) {
      let n = queue.length;
      for(let i = 0; i < n; i++) {
          let node =  queue.shift();
          if(i === n - 1) res.push(node.val);
          node.left && queue.push(node.left);
          node.right && queue.push(node.right);
      }
  }
  return res;
};

时间：O(n)
空间：O(n)

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月3日下午9:23

层序遍历取最后一位

时间复杂度O(N) 节点数目空间复杂度O(N) 辅助队列

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        if(root == null) return ret;
        queue.addLast(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0;i < size;i++){
                TreeNode cur = queue.removeFirst();
                if(i == 0) ret.add(cur.val);
                if(cur.right != null) queue.addLast(cur.right);
                if(cur.left != null) queue.addLast(cur.left);
            }
        }
        return ret;
    }
}

0 赞同 0 条回复

So 普通 2022年11月3日下午8:39

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
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);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                if (i == size - 1) {
                    res.add(node.val);
                }
            }
        }
        return res;
    }
}

时间：O(n)，空间：O(n)

0 赞同 0 条回复

Whatever 永久会员 2022年11月3日下午8:23

层序遍历，每一层遍历时从右向左遍历，每一层的队头则为最右节点，得到右视图。时间O(n)，空间O(n)

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
       List<Integer> list = new LinkedList<>();
       if(root == null){
           return list;
       }
       Queue<TreeNode> q = new LinkedList<>();
       q.offer(root);
       while(!q.isEmpty()){
           int size = q.size();
           TreeNode end = q.peek();
           for(int i = 0;i < size;i++){
               TreeNode cur = q.poll();
               if(cur.right != null){
                   q.offer(cur.right);
               }
               if(cur.left != null){
                   q.offer(cur.left);
               }
           }
           list.add(end.val);
       }
       return list;
    }
}

0 赞同 0 条回复

【二叉树专题】额外补充：199. 二叉树的右视图

共以下 30 个回答

层序遍历，取每层最后一个

# 回答此问题取消回复

【二叉树专题】额外补充：199. 二叉树的右视图

共以下 30 个回答

层序遍历，取每层最后一个

# 回答此问题 取消回复

# 回答此问题取消回复