Java BFS solution with a Queue


  • 0

    It's like an ordinary binary tree level order traversal, and it will stop and the length d.

    public TreeNode addOneRow(TreeNode root, int v, int d) {
    	if (d == 1) {
    		TreeNode newNode = new TreeNode(v);
    		newNode.left = root;
    		return newNode;
    	}
    	bfs(root, v, d);
    	return root;
    }
    
    private void bfs(TreeNode root, int v, int d) {
    	Queue<TreeNode> queue = new LinkedList<>();
    	queue.add(root);
    	int curNum = 1;
    	int nextNum = 0;
    	int level = 1;
    	while (!queue.isEmpty()) {
    		TreeNode node = queue.poll();
    		curNum--;
    		if (level == d - 1) {
    			TreeNode temp = node.left;
    			node.left = new TreeNode(v);
    			node.left.left = temp;
    			temp = node.right;
    			node.right = new TreeNode(v);
    			node.right.right = temp;
    		}
    		if (node.left != null) {
    			queue.add(node.left);
    			nextNum++;
    		}
    		if (node.right != null) {
    			queue.add(node.right);
    			nextNum++;
    		}
    		if (curNum == 0) {
    			curNum = nextNum;
    			nextNum = 0 ;
    			level++;
    		}
    		if (level == d) {
    			break;
    		}
    	}
    }

Log in to reply
 

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