NULL 普通 2024年3月21日下午2:16

class Solution {
List<List> list = new ArrayList<List>();
public List rightSideView(TreeNode root) {
List res = new ArrayList();
order(root,0);
for(int i = 0;i < list.size(); i++){
int len = list.get(i).size();
int val = list.get(i).get(len – 1);
res.add(val);
}
return res;
}
public void order(TreeNode root, int deep){
if(root null)return;
deep++;
if(list.size() < deep){
List item = new ArrayList();
list.add(item);
}
list.get(deep – 1).add(root.val);
order(root.left,deep);
order(root.right,deep);
}
}
收起

0 赞同 0 条回复

紫芝普通 2024年3月18日下午1:49

思路：层序遍历，将每一层的最后一个节点的值存储到结果集中

“`c++
class Solution {
public:
vector rightSideView(TreeNode* root) {
vector ans;
if (root == nullptr) return ans;
queue que;
que.push(root);
while (!que.empty()){
int len = que.size();
for (int i=0; ileft) que.push(cur->left);
if (cur->right) que.push(cur->right);
if (i == len-1) {
ans.push_back(cur->val);
}
}
}
return ans;

};

“`

0 赞同 0 条回复

mpweixin用户普通 2024年3月15日下午10:03

java
class Solution {

    List<Integer> res = new ArrayList<>();

    public List<Integer> rightSideView(TreeNode root){
        dfs(root, 0);
        return res;
    }

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

}
DFS
O(N)
O(N)
提交

0 赞同 0 条回复

言之命至普通 2024年3月15日下午8:39

层次遍历，记录下每层的最后一个元素

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 条回复

kfaebot 普通 2024年3月15日上午10:56

/**
 * 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> answer;
        queue<TreeNode*> que;
        if(root!=nullptr){
            que.push(root);
        }

        while(!que.empty()){
            int size=que.size();

            for(int i=0;i<size;i++){
                TreeNode* tmp=que.front();
                que.pop();

                if(i==size-1){
                    answer.push_back(tmp->val);
                }
                if(tmp->left!=nullptr){
                    que.push(tmp->left);
                }
                if(tmp->right!=nullptr){
                    que.push(tmp->right);
                }
            }
        }
        return answer;
    }
};
//正常层序遍历，但是仅存储每一层最后一个节点的值
//时间复杂度和空间复杂度均为O(N)

0 赞同 0 条回复

神经蛙普通 2024年3月15日上午12:06

class Solution {
public:
vector 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 != NULL) {
            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记录下每一层最右边的节点

0 赞同 0 条回复

Jimmy 普通 2024年3月14日下午10:17

层序遍历，把每一层节点的数值存在一个数组里面，数组最后一个元素就组成了二叉树的右视图

/**
 * 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> ans;
        queue<TreeNode*> que;
        if(root)que.push(root);
        while(!que.empty()){
            int size = que.size();
            vector<int> buffer;
            for(int i=0;i<size;i++){
                TreeNode *cur = que.front();
                que.pop();
                buffer.push_back(cur->val);
                if(cur->left)que.push(cur->left);
                if(cur->right)que.push(cur->right);
            }
            ans.push_back(buffer[size-1]);
        }
        return ans;

    }
};

0 赞同 0 条回复

王位詮釋普通 2024年3月14日下午3:38

class Solution {
    List<Integer> result = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        bfs(root);
        return result;
    }
    public void bfs(TreeNode root){
        if(root<span class="text-highlighted-inline" style="background-color: #fffd38;">null){
            return;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        while(!deque.isEmpty()){
            for(int i=deque.size();i>0;i--){
                TreeNode temp = deque.poll();
                if(i</span>1){
                    result.add(temp.val);
                }
                if(temp.left!=null){
                    deque.offer(temp.left);
                }
                if(temp.right!=null){
                    deque.offer(temp.right);
                }<br />
            }
        }
    }
}
思路：对二叉树进行层序遍历，每一层的最后一个节点就是所需要的节点。

0 赞同 0 条回复

云无深雁影普通 2024年3月14日下午2:50

class Solution {
public List rightSideView(TreeNode root) {
List list = new ArrayList<>();
if(rootnull)
return list;
Queue queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
int size = queue.size();
for(int i = 0; i < size-1; i++){
TreeNode temp = queue.remove();
if(temp.left!=null) queue.add(temp.left);
if(temp.right!=null) queue.add(temp.right);
}
TreeNode temp = queue.remove();
if(temp.left!=null) queue.add(temp.left);
if(temp.right!=null) queue.add(temp.right);
list.add(temp.val);
}
return list;
}
}
//层序遍历时空复杂度均为On

0 赞同 0 条回复

Yuki 永久会员 2024年3月14日上午10:16

层序遍历变体
https://leetcode.cn/problems/binary-tree-right-side-view/solutions/2686065/er-cha-shu-de-you-shi-tu-by-yukislab-85ws

0 赞同 0 条回复

方铎码农普通 2024年3月14日上午9:49

//层序遍历返回最后结果
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        Map<Integer,Integer> rightMostValueAtDepth = new HashMap<Integer,Integer>();
        int max_depth = -1;
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        Queue<Integer> depthQueue = new LinkedList<Integer>();
        nodeQueue.add(root);
        depthQueue.add(0);

        while(!nodeQueue.isEmpty()){
            TreeNode node = nodeQueue.remove();
            int depth = depthQueue.remove();

            if(node != null){
                max_depth = Math.max(max_depth,depth);
                rightMostValueAtDepth.put(depth,node.val);

                nodeQueue.add(node.left);
                nodeQueue.add(node.right);
                depthQueue.add(depth+1);
                depthQueue.add(depth+1);
            }
        }

        List<Integer> res = new LinkedList<>();
        for(int d = 0; d <= max_depth; d++){
            res.add(rightMostValueAtDepth.get(d));
        }
        return res;
    }
}

打卡，注意depthQueue的使用，这是记录队列内节点所在层数的一种方法

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月14日上午8:32

打卡

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(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
                if(i == _size - 1) res.emplace_back(cur->val);
            }
        }
        return res;
    }
};

0 赞同 0 条回复

Yox 普通 2024年3月14日上午2:16

Definition for a binary tree node.

class TreeNode:

def init(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
stack = collections.deque()
resright = []
res = []
stack.append(root)
while stack:
layer = []
for _ in range(len(stack)):
node = stack.popleft()
layer.append(node.val)
if node.left: stack.append(node.left)
if node.right: stack.append(node.right)
res.append(layer[-1])
return res
双o n

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月13日下午11:38

层序遍历的每层最后一个即为右视图

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

        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> res = new ArrayList<>();

        queue.add(root);

        while(!queue.isEmpty()){
            int size=queue.size();
            List<Integer> t = new ArrayList<>();
            for(int i=1;i<=size;i++){
                TreeNode temp=queue.poll();
                t.add(temp.val);
                if(temp.left!=null){
                    queue.add(temp.left);
                }
                if(temp.right!=null){
                    queue.add(temp.right);
                }
            }

            res.add(t.get(t.size()-1));
        }

        return res;

    }
}

0 赞同 0 条回复

heathhou 普通 2024年3月13日下午10:10

class Solution {
public:
    // 使用队列进行辅助中序遍历
    queue<TreeNode*> q;
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        if(root == nullptr){
            return ans;
        }
        q.push(root);
        while(!q.empty()){
            // 获取当前队列内的节点个数，将最后一个节点的值加入vector内
            int size = q.size();

            TreeNode* t;

            for(int i = 0; i < size; ++i){
                t = q.front(); q.pop();
                if(t->left){
                    q.push(t->left);
                }
                if(t->right){
                    q.push(t->right);
                }
            }
            ans.push_back(t->val);  
        }
        return ans;
    }
};

0 赞同 0 条回复

Raphtalia. 普通 2024年3月13日下午9:42

/**
* 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 rightSideView(TreeNode root) {
vector res;
if(!root) return res;
queue<TreeNode> q;
q.push(root);
while(!q.empty()){
int sz = q.size();
for(int i = 0; i < sz; i ++){
TreeNode node = q.front();
q.pop();
if(i 0) res.push_back(node->val);
if(node->right) q.push(node->right);
if(node->left) q.push(node->left);
}
}
return res;
}
};时间复杂度o（n)，空间复杂度O（n)

0 赞同 0 条回复

机电皮怪永久会员 2024年3月13日下午9:34

时间复杂度O(n)
空间复杂度O(1)
想试试深度优先搜索结果没做出来

“`C++
class Solution {
public:
vector rightSideView(TreeNode* root) {
if(root == nullptr)
{
return {};
}

    //广度优先搜索
    vector<int> result;
    queue<TreeNode*> sub;
    TreeNode* temp = root;
    sub.push(temp);

    while(sub.empty() == false)
    {
        //记录每一层的广度
        int count = sub.size();
        for(int i = 0; i < count; i++)
        {
            temp = sub.front();
            sub.pop();
            if(temp->left != nullptr)
            {
                sub.push(temp->left);
            }
            if(temp->right != nullptr)
            {
                sub.push(temp->right);
            }
            if(i == count - 1)
            {
                result.push_back(temp->val);
            }
        }
    }
    return result;
}

};

“`

0 赞同 0 条回复

mpweixin用户普通 2024年3月13日下午9:32

public List rightSideView(TreeNode root) {
List res =new ArrayList<>();
if(rootnull) return res;
Queue q=new LinkedList<>();
q.offer(root);
while(!q.isEmpty()){
int size =q.size();
for(int i=0;i<size;i++){
TreeNode tmp =q.poll();
if(tmp.left!=null) q.offer(tmp.left);
if(tmp.right!=null) q.offer(tmp.right);
if(isize-1) res.add(tmp.val);
}
}
return res;
}
思路：每次层序遍历的最后一个结点就是右边看到的第一个结点层序遍历即可

0 赞同 0 条回复

MARS 普通 2024年3月13日下午9:09

day12第二题

/**
 * 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 []
    let res = []
    let queue = [root]
    let len = 1
    while (queue.length > 0) {
        len = queue.length
        for (let i = 0; i < len; i++) {
            let node = queue.shift()
            if (i == len - 1) res.push(node.val)   //层次遍历，取最后一个
            node.left && queue.push(node.left)
            node.right && queue.push(node.right)
        }
    }
    return res
};

0 赞同 0 条回复

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

共以下 19 个回答

Definition for a binary tree node.

class TreeNode:

def init(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

# 回答此问题取消回复

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

共以下 19 个回答

Definition for a binary tree node.

class TreeNode:

def init(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

# 回答此问题 取消回复

# 回答此问题取消回复