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

小肸永久会员 2023年9月3日下午3:57

class Solution {
    static List<Integer> res = null;
    static Set<Integer> set = null;
    public List<Integer> rightSideView(TreeNode root) {
        res = new ArrayList<>();
        set = new HashSet<>();
        dfs(root, 1);
        return res;
    }
    //中 | 右 | 左进行深搜
    private void dfs(TreeNode node, int level) {
        if (node == null) {
            return;
        }
        //每一层第一次访问的节点就是右边第一个节点
        if (!set.contains(level)) {
            res.add(node.val);
            set.add(level);
        }
        dfs(node.right, level + 1);
        dfs(node.left, level + 1);
    }
}

0 赞同 0 条回复

Sheng 永久会员 2023年9月1日上午11:15

    //二叉树的右视图
    //使用层序遍历
    public List<Integer> rightSideView(TreeNode root) {
        if(root == null) return new LinkedList<Integer>();

        List<Integer> list = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        int size = 0;
        TreeNode node = root;
        queue.add(node);
        while(!queue.isEmpty()) {
            size = queue.size();
            for(int j = 0; j < size; j++) {
                node = queue.remove();
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            list.add(node.val);
        }
        return list;

0 赞同 0 条回复

sc_Yang 普通 2023年8月31日下午2:08

层次遍历，每次只取队列最后一个

/**
 * 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) {
        if(root==nullptr){
            return {};
        }
        vector<int> ret;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            int sizeQ = que.size();
            ret.push_back(que.back()->val);
            for(int i=0; i< sizeQ; ++i){
                TreeNode* tmpnode = que.front();
                if(tmpnode->left!=nullptr) que.push(tmpnode->left);
                if(tmpnode->right!=nullptr) que.push(tmpnode->right);
                que.pop();
            }
        }
        return ret;
    }
};

0 赞同 0 条回复

sincere 普通 2023年8月30日下午10:34

思路：参考剑指 Offer 32 – II. 从上到下打印二叉树，获取到的list中，每个list的最后一个元素即为右视图
复杂度：时间复杂度O(n)，空间复杂度O(n)

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        List<List<Integer>> levelList = levelOrder(root);
        for (List<Integer> subList : levelList) {
            list.add(subList.get(subList.size() - 1));
        }
        return list;
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int count = queue.size();// 本层节点数
            List<Integer> tmpList = new ArrayList<>();
            while (count-- > 0) {
                TreeNode node = queue.poll();
                tmpList.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            list.add(tmpList);
        }
        return list;
    }
}

看别人的题解，直接层序遍历，每层最后一个判断下加入到list即可

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 (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                if (i == size - 1) {
                    list.add(node.val);
                }
            }
        }
    }
}

0 赞同 0 条回复

帝心引力永久会员 2023年8月25日下午8:43

时间o(n), 空间o(n)
vector<int> rightSideView(TreeNode* root) {
        if(root==nullptr) return {};
        vector<int> ans;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            int n = que.size();
            while(n){
                auto node = que.front();
                que.pop();
                if(n==1){
                    ans.emplace_back(node->val);
                }
                if(node->left) que.push(node->left);
                if(node->right)que.push(node->right);
                n--;
            }
        }
        return ans;
    }

0 赞同 0 条回复

c 普通 2023年8月24日下午10:54

层序保存每层最后一个

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

0 赞同 0 条回复

别扒拉我普通 2023年8月24日下午9:47

1、先序遍历变体，根->右->左

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

2、层序遍历，把每层最后一个存进去

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;
    }
}

0 赞同 0 条回复

行动派小彩笔普通 2023年8月24日下午6:37

 //层序遍历思想
 //时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if(!root) return {};
        vector<int> vec;
        deque<TreeNode*> q;
        q.push_back(root);
        while(!q.empty())
        {
            int n = q.size();
            for(int i=n;i>0;--i)
            {
                TreeNode* node = q.front();
                q.pop_front();
                if(i==1) vec.push_back(node->val);
                if(node->left) q.push_back(node->left);
                if(node->right) q.push_back(node->right);
            }
        }

        return vec;
    }
};

0 赞同 0 条回复

JustRtn 普通 2023年8月24日下午3:43

按层遍历，保存每层最后一个值
O(n)

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

        return vec;
    }
};

0 赞同 0 条回复

塔底的仰望永久会员 2023年8月24日下午2:49

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);
        int len = 1;
        while (!queue.isEmpty()) {
            while (len > 0) {
                TreeNode p = queue.poll();
                len--;
                //某层的最后一个节点
                if (len == 0) {
                    list.add(p.val);
                }
                if (p.left != null) {
                    queue.add(p.left);
                }
                if (p.right != null) {
                    queue.add(p.right);
                }
            }
            len = queue.size();
        }
        return list;
    }
}

0 赞同 0 条回复

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

共以下 10 个回答

# 回答此问题取消回复

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

共以下 10 个回答

# 回答此问题 取消回复

# 回答此问题取消回复