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

岱永久会员 2025年1月10日下午4:29

199. 二叉树的右视图

层序遍历。记录每层最后一个

class Solution {
    public List<Integer> rightSideView(TreeNode root) {

        List<Integer> l = new ArrayList<>();
        if(root==null)return l;
        //层序遍历
        Queue<TreeNode> queue =  new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()){
            for(int i = queue.size();i>0;i--){
                TreeNode node = queue.poll();
                if(i==1)l.add(node.val);
                if(node.left!=null) queue.add(node.left);
                if(node.right!=null) queue.add(node.right);
            }

        }
        return l;
    }
}

递归，记录第一次到某深度

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        dfs(root , 0, ans);
        return ans;
    }
    void dfs(TreeNode root,int depth, List<Integer> ans){
        if(root==null)return;
        //深度首次遇到
        if(depth == ans.size()) ans.add(root.val);
        dfs(root.right,depth+1,ans);
        dfs(root.left,depth+1,ans);
    }

}

0 赞同 0 条回复

mpweixin用户普通 2024年12月24日下午10:36

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        if(root == NULL) return result;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int num = q.size();
            int vals = 0;
            while(num != 1){
                TreeNode* temp = q.front();
                q.pop();
                if(temp->left) q.push(temp->left);
                if(temp->right) q.push(temp->right);
                num--;
            }
            TreeNode* temp = q.front();
            q.pop();
            if(temp->left) q.push(temp->left);
            if(temp->right) q.push(temp->right);
            result.push_back(temp->val);
        }

        return result;
    }
};

层序遍历，只记录每层最后的节点即可。

0 赞同 0 条回复

陆狗陆狗普通 2024年12月8日下午9:43

解题思路
– 按层打印的基础上，按每一层分组，并且找到这一层的最后一个节点即可
【题解1】

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result=new ArrayList();
        if(root==null){
           return result; 
        }
        Queue<TreeNode> q=new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            int size=q.size();
            // 内部单独进行每一层的循环
            while(size-->0){
                TreeNode current= q.poll();
                // size==0说明是本层最后一个节点
                if(size==0){
                    result.add(current.val);
                }
                // 左右节点放入队列
                if(current.left!=null){
                    q.offer(current.left);
                }
                if(current.right!=null){
                    q.offer(current.right);
                }
            }
        }
        return result;
    }
}

0 赞同 0 条回复

Renasc 普通 2024年12月6日下午10:30

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

class Solution {
    List<Integer> answer;
    public List<Integer> rightSideView(TreeNode root) {
        answer = new ArrayList<>();
        dfs(root, 0);  // 深度优先遍历
        return answer;
    }

    // 深度优先遍历
    private void dfs(TreeNode root, int depth) {
        if (root == null) return;
        if (answer.size() <= depth) {
            answer.add(root.val);   // 只有answer小于等于深度的时候，才是最右边的节点
        }
        // 遍历右左子树
        dfs(root.right, depth+1);
        dfs(root.left, depth+1);
    }
}

0 赞同 0 条回复

黑键〰普通 2024年12月5日下午5:27

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function(root) {
    if(root == null) return []
    // 层序遍历，但是从右往左push进队列
    let q = [root]
    let res = []
    while(q.length > 0) {
        res.push(q[0].val)
        let len = q.length
        while(len) {
            let cur = q.shift()
            if(cur.right != null) q.push(cur.right) 
            if(cur.left != null) q.push(cur.left) 
            len--
        }
    }
    return res
};

思路：层序遍历，但是从右往左push进队列
只在每一层刚进入时对结果数组中放入val

0 赞同 0 条回复

晓宇普通 2024年12月5日下午12:05

class Solution {
public:

    // 使用层序遍历，每层最右侧节点为右视图节点
    vector<int> rightSideView(TreeNode* root) {
        if(root == nullptr) return vector<int> ();
        vector<int> ans;  // 储存右视图节点
        queue<TreeNode*> qT; // 用于层序遍历的队列
        qT.push(root);
        while(!qT.empty()){
            int size = qT.size(); // 记录当前层节点数
            TreeNode* last;  // 记录当前层最后一个节点
            for(int i = 0;i < size;i ++){
                TreeNode* temp = qT.front();
                qT.pop();  // o(1)
                last = temp;
                if(temp->left)  qT.push(temp->left);
                if(temp->right) qT.push(temp->right);
            }
            ans.push_back(last->val);
        }
        return ans;
    }
    // 时间复杂度: o(n); 空间复杂度: o(n)
};

0 赞同 0 条回复

苯庸普通 2024年12月4日下午7:28

class Solution {
public List rightSideView(TreeNode root) {
List res = new ArrayList();
if(root null) return res;
Queue queue = new LinkedList();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
int right = 0;
while(size– > 0){
TreeNode tmp = queue.poll();
right = tmp.val;
if(tmp.left != null) queue.offer(tmp.left);
if(tmp.right != null) queue.offer(tmp.right);
}
res.add(right);
}
return res;
}
}
思路：层次遍历，记录每个数，这样正好可以记录到每层的最后一个树，然后添加到队列中
时间：O（n）
空间：O（n）

0 赞同 0 条回复

Kisara 普通 2024年12月4日下午6:41

广度优先搜索，每一层的最后一个节点就是右视图，还有一种方法是深度优先搜索，先右后左，每一层便利的第一个节点就是答案，前提是这一层没有遍历过

/**
 * 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) {
        Queue<TreeNode> queue=new LinkedList<>();
        List<Integer> list=new ArrayList<>();
        if(root==null) return list;
        queue.add(root);
        int count;
        while(!queue.isEmpty()){
            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) list.add(node.val);
            }
        }
        return list;
    }
}

on on

0 赞同 0 条回复

Aatorx 永久会员 2024年12月4日下午5:19

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

分层层序遍历二叉树，只保存每一层最后一个节点的数值。
时间复杂度O(N)，空间复杂度O(N)。

0 赞同 0 条回复

Xiang. 永久会员 2024年12月4日下午4:25

思路：在分层保存二叉树题目的基础上，只向队列中加入非空结点，那么，每层第len-1个结点则为最右结点
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 len=queue.size();
            for(int i=0;i<len;i++){
                TreeNode tmp=queue.poll();
                if(tmp.left!=null)queue.offer(tmp.left);
                if(tmp.right!=null)queue.offer(tmp.right);
                if(i==len-1) res.add(tmp.val);
                }
            }
        return res;
        }

}
时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

lQl 永久会员 2024年12月3日下午10:40

先层序遍历,取每层最后一个节点

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

            TreeNode node = q.poll();
            ans.add(node.val);
            if(node.left!=null)q.add(node.left);
            if(node.right!=null)q.add(node.right);
        }
        return ans;
    }
}

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

0 赞同 0 条回复

jaron 普通 2024年12月3日下午10:30

LCR 149. 彩灯装饰记录 I – 力扣（LeetCode）的变形，层次遍历收集每层的最后一个节点

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList();
        List<Integer> ans = new ArrayList();
        if (root == null) {
            return ans;
        }
        queue.add(root);
        while (!queue.isEmpty()) {
            int k = queue.size();
            for (int i = 0; i < k; i++) {
                TreeNode temp = queue.poll();
                if (temp.left != null)
                    queue.add(temp.left);
                if (temp.right != null)
                    queue.add(temp.right);
                // 如果是每一层最后一个就加进去
                if (i == k - 1)
                    ans.add(temp.val);
            }
        }
        return ans;
    }
}

0 赞同 0 条回复

迢迢星野普通 2024年12月3日下午8:41

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> que = new LinkedList<>();
        que.offer(root);

        while (!que.isEmpty()) {
            int size = que.size();
            // 每一层的最后一个节点就是其最右侧节点
            TreeNode last = que.getLast();
            for (int i = 0; i < size; i++) {
                TreeNode node = que.poll();
                if (node.left != null) {
                    que.offer(node.left);
                }
                if (node.right != null) {
                    que.offer(node.right);
                }
            }
            res.add(last.val);
        }
        return res;        
    }
}

思路：层序遍历，每一层的最后一个节点就是所求的右视图节点。
时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

月下足迹普通 2024年12月3日下午8:38

//层序遍历，只输出每一层最右边的数
class Solution {
private List<List> arr;
private Queue q;
private List result;

public List<Integer> rightSideView(TreeNode root) {
    arr = new ArrayList<>();
    q = new LinkedList<>();
    result = new ArrayList<>();

    if (root == null) {
        return result;
    }else {
        q.offer(root);
    }

    while (!q.isEmpty()) {
        List<Integer> larryArr = new ArrayList<>();
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode temp = q.poll();
            larryArr.add(temp.val);
            if(temp.left!=null) q.offer(temp.left);
            if(temp.right!=null) q.offer(temp.right);
        }
        arr.add(larryArr);
    }
    for (int j = 0; j < arr.size(); j++) {
         result.add(arr.get(j).getLast());
    }
    return result;
}

}

0 赞同 0 条回复

Jerry 普通 2024年12月3日下午8:19

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

层序遍历，当遇到这一层最后一个元素是，push进结果数组中。

0 赞同 0 条回复

秋山丽奈普通 2024年12月3日下午8:08

思路：使用层次遍历记录每层最后一个节点

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

        // 层次遍历 记录每层最后一个 
        List<TreeNode> nodeList = new ArrayList<>();

        nodeList.add(root);
        List<TreeNode> nextList ;

        while(nodeList.size() != 0 ){
            // 记录上一棵树最后结点 
            ans.add(nodeList.get(nodeList.size()-1).val);

            nextList = new ArrayList<>();
            for(TreeNode current: nodeList){
                if(current.left != null){
                    nextList.add(current.left);
                }

                if(current.right != null){
                    nextList.add(current.right);
                }
            }

            nodeList = nextList;

        }

        return ans;

    }
}

0 赞同 0 条回复

【二叉树专题】199. 二叉树的右视图

共以下 16 个回答

199. 二叉树的右视图

# 回答此问题取消回复

【二叉树专题】199. 二叉树的右视图

共以下 16 个回答

199. 二叉树的右视图

# 回答此问题 取消回复

# 回答此问题取消回复