[LeetCode]199.Binary Tree Right Side View

偏执的太偏执、 2022-02-01 19:41 130阅读 0赞

**题目**

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:  
Given the following binary tree,  
1 <—  
/ \\  
2 3 <—  
\\ \\  
5 4 <—  
You should return \[1, 3, 4\].

**思路**

层次遍历

**代码**

/*-------------------------------------------------------------------
        *   日期：2014-04-05
        *   作者：SJF0115
        *   题目: 199.Binary Tree Right Side View
        *   来源：https://leetcode.com/problems/binary-tree-right-side-view/
        *   结果：AC
        *   来源：LeetCode
        *   总结：
        --------------------------------------------------------------------*/
        #include <iostream>
        #include <vector>
        #include <queue>
        using namespace std;
    
        struct TreeNode{
            int val;
            TreeNode *left;
            TreeNode *right;
            TreeNode(int x) : val(x), left(NULL), right(NULL) {}
        };
    
        class Solution {
        public:
            vector<int> rightSideView(TreeNode *root) {
                vector<int> result;
                if(root == nullptr){
                    return result;
                }//if
                queue<TreeNode*> cur;
                queue<TreeNode*> next;
                cur.push(root);
                result.push_back(root->val);
                TreeNode *node,*pre;
                // 层次遍历
                while(!cur.empty()){
                    pre = nullptr;
                    while(!cur.empty()){
                        node = cur.front();
                        cur.pop();
                        if(node->left){
                            next.push(node->left);
                            pre = node->left;
                        }//if
                        if(node->right){
                            next.push(node->right);
                            pre = node->right;
                        }//if
                    }//while
                    if(pre != nullptr){
                       result.push_back(pre->val);
                    }//if
                    swap(cur,next);
                }//while
                return result;
            }
        };
    
    int main() {
        Solution solution;
        TreeNode *root = new TreeNode(1);
        root->left = new TreeNode(2);
        root->right = new TreeNode(3);
        root->left->right = new TreeNode(5);
        root->right->right = new TreeNode(4);
        vector<int> result = solution.rightSideView(root);
        for(int i = 0;i < result.size();++i){
            cout<<result[i]<<" ";
        }//for
        cout<<endl;
        return 0;
    }

**运行时间**

![这里写图片描述][20150405205941010]

[20150405205941010]: /images/20220126/b6a9c9974e2c4f529483c28269d0aec3.png