本文共 1540 字,大约阅读时间需要 5 分钟。
A simple application of level-order traversal. Just push the last node in each level into the result.
The code is as follows.
1 class Solution { 2 public: 3 vector rightSideView(TreeNode* root) { 4 vector right; 5 if (!root) return right; 6 queuetoVisit; 7 toVisit.push(root); 8 while (!toVisit.empty()) { 9 TreeNode* rightNode = toVisit.back();10 right.push_back(rightNode -> val);11 int num = toVisit.size();12 for (int i = 0; i < num; i++) {13 TreeNode* node = toVisit.front();14 toVisit.pop();15 if (node -> left) toVisit.push(node -> left);16 if (node -> right) toVisit.push(node -> right);17 }18 }19 return right;20 }21 };
Well, the above code is of BFS. This problem can still be solved using DFS. The code is as follows. Play with it to see how it works :-)
1 class Solution { 2 public: 3 vector rightSideView(TreeNode* root) { 4 vector right; 5 if (!root) return right; 6 rightView(root, right, 0); 7 } 8 private: 9 void rightView(TreeNode* node, vector & right, int level) {10 if (!node) return;11 if (level == right.size())12 right.push_back(node -> val);13 rightView(node -> right, right, level + 1);14 rightView(node -> left, right, level + 1);15 }16 };
转载地址:http://ckuix.baihongyu.com/