leetcode Binary Tree Right Side

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].

这是一道medium的题，但是刚开始感觉不难。首先看到这道题的第一反应就是层序遍历，用队列。以前考研的时候看到过层序遍历，不过真心不记得了。后来自己想偏了，又说想用栈。

这道题就是把每一层的节点从左到右的入队（此时就可以计算一下队的大小，这个我一直没有想到，这样就可以计算出每一层有多少个节点了。），然后取最后一个节点的值入结果vector。假设我们第一层扫描完了（即它的孩子已经入队了），每扫描完了以后就会删掉你扫描的节点，那么当你把第一层的节点扫描完，第二层节点已经入队且第一层的节点已经被删除掉了，此时队列里只有第二层的节点，然后我们取最后一个的值入结果vector，就是最右的（因为我们是从左到右入队的）。同理，扫描第二层节点，扫描完了以后第二层节点已经全部被删除，队列里只有第三层节点。直至队列里没有节点了，说明新的一层一个节点没有，那就是树到底了。附代码。（这道题自己没做出来，后来参考别人的。。）

using namespace std;

/**

 * Definition for a binary tree node.

 * 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) {

        int val=,sizequeue=;

        vector<int> result;

        if(root==NULL) return result;

        queue<TreeNode> TreeQueue;

        TreeQueue.push(*root);

        while(!TreeQueue.empty()){

            val=(TreeQueue.back()).val;

            result.push_back(val);

            sizequeue=TreeQueue.size();

            for(int i=;i<sizequeue;i++){

           *root=TreeQueue.front();

           TreeQueue.pop();

                if(root->left!=NULL)  TreeQueue.push(*(root->left));

                if(root->right!=NULL) TreeQueue.push(*(root->right));

        }

    }

    return result;

}

};

巴特西

leetcode Binary Tree Right Side

最新文章

热门文章