JAVA Solution, DFS and BFS


  • 1
    F

    Time flies! After three months later, when I met this question again, I solve it with totally different way. My previous version is DFS, now I solve it with BFS. Just wondering several months later when I met this question again, which method will I use. lol
    DFS version:

    public class Solution {
        public TreeNode addOneRow(TreeNode root, int v, int d) {
            if(d == 1){
                TreeNode dummy = new TreeNode(v);
                dummy.left = root;
                return dummy;
            }
            helper(root, v, d, 1);
            return root;
        }
        public void helper(TreeNode root,int v, int d, int cur){
            if(root == null) return;
            if(cur == d - 1){
                TreeNode temp = new TreeNode(v);
                temp.left = root.left;
                root.left = temp;
                TreeNode temp2 = new TreeNode(v);
                temp2.right = root.right;
                root.right = temp2;
                return;
            }
            helper(root.left, v, d, cur + 1);
            helper(root.right, v, d, cur + 1);
        }
    }
    

    BFS version:

    class Solution {
        public TreeNode addOneRow(TreeNode root, int v, int d) {
            if (d == 1) {
                TreeNode newRoot = new TreeNode(v);
                newRoot.left = root;
                return newRoot;
            }
            Queue<TreeNode> queue = new LinkedList();
            queue.offer(root);
            int depth = 1;
            while (!queue.isEmpty()) {
                if (depth != d - 1){
                    int size = queue.size();
                    for (int i = 0; i < size; i++){
                        TreeNode node = queue.poll();
                        if (node.left != null) {
                            queue.offer(node.left);
                        }
                        if (node.right != null) {
                            queue.offer(node.right);
                        }
                    }
                    depth++;
                } else {
                    int size = queue.size();
                    for (int i = 0; i < size; i++){
                        TreeNode node = queue.poll();
                        TreeNode newLeft = new TreeNode(v);
                        newLeft.left = node.left;
                        node.left = newLeft;
                        TreeNode newRight = new TreeNode(v);
                        newRight.right = node.right;
                        node.right = newRight;
                    }
                    break;
                }
            }
            return root;
        }
    }
    

Log in to reply
 

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