4ms Easy C++ BFS and DFS Solutions


  • 4

    A simple application of level-order traversal. Just push the last node in each level into the result.

    The code is as follows.

    class Solution {
    public:
        vector<int> rightSideView(TreeNode* root) {
            vector<int> right;
            if (!root) return right;
            queue<TreeNode*> toVisit;
            toVisit.push(root);
            while (!toVisit.empty()) {
                TreeNode* rightNode = toVisit.back();
                right.push_back(rightNode -> val);
                int num = toVisit.size();
                for (int i = 0; i < num; i++) {
                    TreeNode* node = toVisit.front();
                    toVisit.pop();
                    if (node -> left) toVisit.push(node -> left);
                    if (node -> right) toVisit.push(node -> right); 
                }
            }
            return right;
        }
    };
    

    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 :-)

    class Solution {
    public:
        vector<int> rightSideView(TreeNode* root) {
            vector<int> right;
            if (!root) return right;
            rightView(root, right, 0);
        }
    private:
        void rightView(TreeNode* node, vector<int>& right, int level) {
            if (!node) return;
            if (level == right.size())
                right.push_back(node -> val);
            rightView(node -> right, right, level + 1);
            rightView(node -> left, right, level + 1); 
        }
    };

  • 0
    Z

    The DFS one is really smart!


  • 0

    Hi, Zhuzeng. I also like the DFS solution :-)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.