C++ BFS and DFS Solution


  • 0

    DFS need to traverse the whole tree, but BFS not, so BFS solution get better performance than DFS's.

    DFS solution:

    class Solution {
    public:
        void dfs(TreeNode* node, int v, int d, int cur) {
            if (!node) return;
            if (cur == d) {
                TreeNode *l = new TreeNode(v);
                l->left = node->left;
                node->left = l;
    
                TreeNode *r = new TreeNode(v);
                r->right = node->right;
                node->right = r;
                return;
            }
            dfs(node->left, v, d, cur + 1);
            dfs(node->right, v, d, cur + 1);
        }
        TreeNode* addOneRow(TreeNode* root, int v, int d) {
            if (d == 1) {
                TreeNode *newRoot = new TreeNode(v);
                newRoot->left = root;
                return newRoot;
            }
            dfs(root, v, d, 2);
            return root;
        }
    };
    

    BFS solution:

    class Solution {
    public:
        TreeNode* addOneRow(TreeNode* root, int v, int d) {
            if (d == 1) {
                TreeNode *newRoot = new TreeNode(v);
                newRoot->left = root;
                return newRoot;
            }
            --d;
            queue<TreeNode*> q;
            TreeNode *t = nullptr;
            q.push(root);
            while (!q.empty()) {
                int size = q.size();
                if (--d == 0) {
                    while (size--) {
                        t = q.front(); q.pop();
                        TreeNode *l = new TreeNode(v);
                        TreeNode *r = new TreeNode(v);
                        l->left = t->left; t->left = l;
                        r->right = t->right; t->right = r;
                    }
                    break;
                }
                while (size--) {
                    t = q.front(); q.pop();
                    if (t->left) q.push(t->left);
                    if (t->right) q.push(t->right);
                }
            }
            return root;
        }
    };
    

Log in to reply
 

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