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

ppopp 普通 2023年8月27日下午9:35

/**
* 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 {
private:
vector ans;

public:
vector rightSideView(TreeNode* root) {
vector<vector> res;
if(!root) return {};

    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()){
        //目前队列的长度为这一层的节点数
        int cur = q.size();
        //将这一层的结点
        res.push_back(vector<int> ());
        for(int i = 1; i <= cur; i++){
            //出队
            auto node = q.front();
            q.pop();
            //利用刚送入数组后端的数组，放入结点的数值
            res.back().push_back(node->val);
            if(i == cur) ans.push_back(node->val);
            //左右子树结点入队
            if(node->left) q.push(node->left);
            if(node->right) q.push(node->right);
        }
    }
    return ans;
}

};

0 赞同 0 条回复

hi 普通 2023年8月15日上午8:53

答案为层序遍历时每层的最右那个数

/**
 * 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) {
        queue<TreeNode*> q;
        vector<int> res;

        if(root) q.push(root);

        while(q.size()){
            int len = q.size();
            for(int i = 0; i < len; i++)
            {
                TreeNode* t = q.front();
                q.pop();
                if(t -> left) q.push(t->left);
                if(t -> right) q.push(t -> right);
                if(i == len - 1) res.push_back(t->val);
            }
        }
        return res;
    }
};

0 赞同 0 条回复

片言莫语普通 2023年8月3日下午3:04

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

doordie. 普通 2023年8月2日上午11:31

层序遍历，每层最后一个节点的值存储下来

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        // 特殊情况
        if (root == null) {
            return new ArrayList<>();
        }
        // 初始化
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        List<Integer> res = new ArrayList<>();
        // 算法流程
        while (!queue.isEmpty()) {
            TreeNode node  = new TreeNode();
            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);
               }

           }
           // 循环结束最后一个节点出队 存储值
            res.add(node.val);

        }
        return res;
    }
}

时间复杂度On 代表二叉树的节点值
空间复杂度On

0 赞同 0 条回复

CaCO3 永久会员 2023年7月29日下午5:00

”’java
class Solution {
public List rightSideView(TreeNode root){
Map<Integer,Integer> rightValue = new HashMap<>();
int max_depth = -1;
Deque nodeStack = new LinkedList<>();
Deque depthStack = new LinkedList<>();
nodeStack.push(root);
depthStack.push(0);

   while(!nodeStack.isEmpty()){
       TreeNode node = nodeStack.pop();
       int depth = depthStack.pop();
       if(node != null){
           //维护二叉树的最大深度
           max_depth = Math.max(max_depth,depth);
           //不存在对应深度的结点时才插入
           if(!rightValue.containsKey(depth)){
               rightValue.put(depth,node.val);
           }
           nodeStack.push(node.left);
           nodeStack.push(node.right);
           depthStack.push(depth+1);
           depthStack.push(depth+1);
       }
   }
   List<Integer> rightView = new ArrayList<>();
   for(int depth = 0;depth <= max_depth;depth++){
       rightView.add(rightValue.get(depth));
   }
   return rightView;
}

}
时间复杂度O(n)
空间复杂度O(n)
”’

0 赞同 0 条回复

北辰普通 2023年7月26日下午7:20

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

思路：层序遍历二叉树，然后将每层的最后一个节点加入结果集中就可以
时间复杂度：O（n）
空间复杂度：O（n）

0 赞同 0 条回复

神经蛙普通 2023年7月25日下午9:58

class Solution {

    public List<Integer> rightSideView(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();

        if (root == null) {
            return res;
        }

        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        // 层序遍历，每层拿最后一个值
        while(!queue.isEmpty()) {
            int length = queue.size();
            for (int i = 0; i < length; ++i) {

                TreeNode node = queue.removeFirst();
                if ( i == length - 1) {
                    res.add(node.val);
                }
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }

        }

        return res;
    }


}

0 赞同 0 条回复

CKX 普通 2023年7月24日下午2:16

func rightSideView(root *TreeNode) []int {
    //递归记录深度，深度等于答案的长度，记录到结果集中
    var traverse func(*TreeNode, int)
    ans := []int{}
    traverse = func(root *TreeNode, depth int) {
        if root == nil {
            return
        }
        if depth == len(ans) {
            ans = append(ans, root.Val)
        }
        traverse(root.Right, depth+1)
        traverse(root.Left, depth+1)
    }
    traverse(root, 0)
    return ans
}

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

0 赞同 0 条回复

普通 2023年7月23日下午11:07

C++代码层次遍历做一些改进
class Solution {
vector rightV;
queue<TreeNode> inqueue;
public:
vector rightSideView(TreeNode root)
{
if(!root) return rightV;
rightV.push_back(root->val);
inqueue.push(root);
while(inqueue.size())
{
int l=inqueue.size();
int rr=-1;
for(int i=0;i<l;i++)
{ TreeNode* te=inqueue.front();
inqueue.pop();
if(te->left) inqueue.push(te->left);
if(te->right) inqueue.push(te->right);
if(te->left)
rr=te->left->val;
if(te->right)
rr=te->right->val;
}
if(rr!=rightV.back()&&rr!=-1) rightV.push_back(rr);
}
return rightV;
}
};

0 赞同 0 条回复

今天你刷题了嘛普通 2023年7月23日下午10:44

/**
 * 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> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root==null) return result;
        queue.offer(root);
        while(!queue.isEmpty()){
            // 控制每层的遍历
            int size = queue.size();
            for(int i=0;i<size;i++){
                TreeNode temp = queue.poll();
                if(temp.left!=null) queue.offer(temp.left);
                if(temp.right!=null) queue.offer(temp.right);
                if(i==size-1) result.add(temp.val);
            }
        }
        return result;

    }
}

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

0 赞同 0 条回复

周小二普通 2023年7月23日下午2:31

//层序遍历
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        if (root == null) {
            return new ArrayList<Integer>();
        }
        List<Integer> list = new ArrayList<>();
        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(Integer.valueOf(node.val));
                }
                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return list;
    }
}

0 赞同 0 条回复

June 普通 2023年7月21日下午4:43

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rightSideView(root *TreeNode) []int {
    var rView []int 
    if root == nil {
        return rView
    }

    var queue = list.New()
    queue.PushBack(root)

    for queue.Len() != 0 {
        size := queue.Len()
        var tmp []int

        for i:=0 ; i < size ; i++ {
            var node *TreeNode = queue.Front().Value.(*TreeNode)
            queue.Remove(queue.Front())
            tmp = append(tmp,node.Val)
            if node.Left != nil {
                queue.PushBack(node.Left)
            }
            if node.Right != nil {
                queue.PushBack(node.Right)
            }
        }
        rView = append(rView,tmp[len(tmp)-1])
    }

    return rView
}

层序遍历

0 赞同 0 条回复

人生何处不青山普通 2023年7月21日上午11:41

层序遍历

function rightSideView(root: TreeNode | null): number[] {
    const res: number[] = [];
    let hh = 0, tt = -1;
    const queue: TreeNode[] = [];
    if (root) queue[++tt] = root;
    while (hh <= tt) {
        let len = tt - hh + 1;
        res.push(queue[tt].val);
        while (len--) {
            let cur = queue[hh++];
            cur.left && (queue[++tt] = cur.left);
            cur.right && (queue[++tt] = cur.right);
        }
    }
    return res;
};

0 赞同 0 条回复

AD钙奶普通 2023年7月21日上午9:19

回溯解法：

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

        backTracking(root,0);
        return list;
    }

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

        if(depth == list.size()) {
            list.add(root.val);
        }
        backTracking(root.right, depth + 1);
        backTracking(root.left, depth + 1);
    }
}

层序遍历解法：

class Solution {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> deque = new ArrayDeque<>();
    public List<Integer> rightSideView(TreeNode root) {
        if(root == null) return res;
        deque.addLast(root);
        while(!deque.isEmpty()) {
            int size = deque.size();
            for(int i = 0; i < size; i ++) {
                TreeNode node = deque.removeFirst();
                if(i == size - 1) {
                    res.add(node.val);
                }
                if(node.left != null) deque.addLast(node.left);
                if(node.right != null) deque.addLast(node.right);
            }
        }
        return res;
    }
}

0 赞同 0 条回复

#00456B 普通 2023年7月20日下午11:46

思路

就是层序遍历的那一套，只是只存最后这一个节点的值。

代码

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

0 赞同 0 条回复

枫梓。普通 2023年7月20日下午2:47

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

按从右到左层次遍历，每层拿出第一个结点值即可。时间O(n) 空间O(n)

0 赞同 0 条回复

mpweixin用户普通 2023年7月20日下午2:38

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

        // 层序遍历取每一层的最后一个元素即可
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> res = new ArrayList<>();
        if (root==null) {
            return res;
        }
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                if (i==size-1) {
                    TreeNode poll = queue.poll();
                    res.add(poll.val);
                    if (poll.left!=null) queue.offer(poll.left);
                    if (poll.right!=null) queue.offer(poll.right);
                } else {
                    TreeNode poll = queue.poll();
                    if (poll.left!=null) queue.offer(poll.left);
                    if (poll.right!=null) queue.offer(poll.right);
                }
            }


        }
        return res;

    }
}

0 赞同 0 条回复

Marshan 普通 2023年7月20日上午11:11

层序遍历, 将每层最后一个节点放入vector

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        if(root == nullptr){
            return res;
        }

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

0 赞同 0 条回复

V2ero 普通 2023年7月20日上午9:15

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

function rightSideView(root: TreeNode | null): number[] {
    if(!root){
        return []
    }
    const ans = [];
    const queue = [root];
    while(queue.length){
        const len = queue.length;
        for(let i = 0; i < len; i += 1){
             const node = queue.shift();
             if(node.left){
                 queue.push(node.left)
             }
            if(node.right){
                 queue.push(node.right)
             }
             // 每一层只放进最后一个节点的值
             if(i === len - 1){
                 ans.push(node.val)
             }
        }
    }
    return ans;
};

0 赞同 0 条回复

Luminous 普通 2023年7月20日上午12:16

/**
 * 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) {
        if(root==null) return new ArrayList<Integer>();
        List<Integer> res=new ArrayList<>();
        Queue<TreeNode> q=new LinkedList<>();
        q.add(root);
        TreeNode last=new TreeNode();
        while(!q.isEmpty()){
            for(int i=q.size();i>0;i--){
                TreeNode node=q.poll();
                if(i==1) last=node;//保存每一层中最后一个取出来的结点
                if(node.left!=null){
                    q.add(node.left);
                }
                if(node.right!=null){
                    q.add(node.right);
                }
            }
            res.add(last.val);
        }
        return res;
    }
}

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

0 赞同 0 条回复

艺普通 2023年7月19日下午10:41

“`c++
class Solution {
public:
vector rightSideView(TreeNode* root) {
queue q;
q.push(root);
vector ans;
if(q.front()==nullptr) return ans;
while(!q.empty())//层次遍历
{
int k=q.size();
for(int i=0;ival);
if(tmp->right) q.push(tmp->right);
if(tmp->left) q.push(tmp->left);
}
}
return ans;
}
};

0 赞同 0 条回复

阿尚普通 2023年7月19日下午9:45

//层次遍历
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while(!queue.isEmpty()){
            int layerSize = queue.size();

            for(int i = 0; i < layerSize; i++){
                TreeNode node = queue.poll();
                if(i == layerSize - 1) result.add(node.val);

                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
        }

        return result;
    }
}

0 赞同 0 条回复

ONE PIECE 普通 2023年7月19日下午8:50

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

时间复杂度：

0 赞同 0 条回复

土豆芋泥包_ 普通 2023年7月19日下午8:01

代码

class Solution {

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

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

0 赞同 0 条回复

Mby 普通 2023年7月19日下午6:56

/**
 * 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<>();
        nextRight(root, res, 0);
        return res;
    }

    private void nextRight(TreeNode root, List<Integer> res, int depth){
        if(root != null){
            if(depth == res.size()){
                res.add(root.val);
            }
            if(root.right != null){//向右边找
                nextRight(root.right, res, depth + 1);
            }
            if(root.left != null){//右子树不存在就往左找
                nextRight(root.left, res, depth + 1);
            }
        }
    }
}

0 赞同 0 条回复

波雅汉库克普通 2023年7月19日下午4:52

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

时间： O（N)
空间； o (n)

0 赞同 0 条回复

NullPointerException 普通 2023年7月19日下午4:30

class Solution {
public List rightSideView(TreeNode root) {
//层序遍历加入每一行的最右边
List result =new ArrayList();
if(root null)
{
return result;
}
Queue queue =new LinkedList();
queue.add(root);
while(!queue.isEmpty())
{
int i =queue.size();
TreeNode temp;
while(i>0)
{
temp = queue.remove();
i–;
if(i0)
{
result.add(temp.val);
}
if(temp.left!=null)
{
queue.add(temp.left);
}
if(temp.right!=null)
{
queue.add(temp.right);
}

            }

        }
        return result;

}

}

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月19日下午2:29

Day12：下面是代码

/**
 * 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> 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; //该dfs结束
        if(depth == res.size()){
            res.add(root.val);
        }
        depth++;
        dfs(root.right, depth);
        dfs(root.left, depth);
    }
}

0 赞同 0 条回复

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

共以下 28 个回答

思路

代码

# 回答此问题取消回复

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

共以下 28 个回答

思路

代码

# 回答此问题 取消回复

# 回答此问题取消回复