和层有关,显然bfs。记录每一个节点的层数,每次用新加入队列节点的值更新当前层的答案。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ struct Node { int layer; TreeNode *node; Node(int l, TreeNode *nd) : layer(l), node(nd) {}; }; class Solution { public: vector<int> rightSideView(TreeNode *root) { vector<int> res; queue<Node> que; if(root == NULL) return res; que.push(Node(0, root)); while(!que.empty()) { Node cur = que.front(); que.pop(); if(res.size() > cur.layer) res[cur.layer] = cur.node ->val; else res.push_back(cur.node ->val); if(cur.node ->left != NULL) que.push(Node(cur.layer + 1, cur.node ->left)); if(cur.node ->right != NULL) que.push(Node(cur.layer + 1, cur.node ->right)); } return res; // 第一次提交的时候这里忘记返回竟然也通过了.. } }; |
Comments are closed.