Simple O(n) Iterative (BFS) Solution


  • 0
    public TreeNode AddOneRow(TreeNode root, int v, int d)
    {
        if (d == 1)
        {
            TreeNode res = new TreeNode(v);
            res.left = root;
            return res;
        }
        Queue<TreeNode> q = new Queue<TreeNode>();
        q.Enqueue(root);
        int level = 1;
        while (q.Any() && level < d) //while queue is not empty
        {
            int count = q.Count;
            while (count != 0) //in the same level
            {
                TreeNode curr = q.Dequeue();
                if (level == d - 1)
                {
                    TreeNode templeft = curr.left;
                    TreeNode tempright = curr.right;
                    TreeNode newleft = new TreeNode(v);
                    TreeNode newright = new TreeNode(v);
                    newleft.left = templeft;
                    newright.right = tempright;
                    curr.left = newleft;
                    curr.right = newright;
                }
                if (curr.left != null) q.Enqueue(curr.left);
                if (curr.right != null) q.Enqueue(curr.right);
                count--;
            }
            level++;
        }
        return root;
    }
    

Log in to reply
 

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