[LeetCode]199.Binary Tree Right Side View

题目

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

运行时间

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>