Find the deepest node in a binary tree; Build a tree out of given edges; etc

Question

Swaraj · Accepted Answer

import java.util.LinkedList;
import java.util.Queue;

public class DeepestNode {
	
	public static TNode deepestNode(BST b)
	{
		TNode root=b.root;
		if(root==null)
			return null;
		Queue nodes=new LinkedList();
		Queue count=new LinkedList();
		nodes.add(root);
		TNode cur=null;
		while(!nodes.isEmpty())
		{
			 cur=nodes.poll();
			if(cur.left!=null)
				nodes.add(cur.left);
			if(cur.right!=null)
				nodes.add(cur.right);
			
		}
		return cur;
	}
	public static void main(String[] args) {
		BST b=new BST();
		b.insert(6); b.insert(2); b.insert(10); b.insert(-1); b.insert(3); b.insert(8); b.insert(17); b.insert(15);b.insert(13); b.insert(16);
		TNode op=deepestNode(b);
		if(op!=null)
			System.out.println(op.data);
	}

}






public class TNode{
	int data;
	TNode left;
	TNode right;
	TNode()
	{
		
	}
	TNode(int d)
	{
		data=d;
		left=null;
		right=null;
	}
}

ib · Answer

int max = 0;
	Node answer = null;
	Node previous = null;

	public Node deepestNode(Node node) {
		maxDepth(node, 0);
		return answer;
	}

	private void maxDepth(Node node, int depth) {
		if (node == null) {
			if (depth > max) {
				max = depth - 1;
				answer = previous;
			}
		}
		previous = node;
		return Math.max(maxDepth(node.left, depth + 1), maxDepth(node.right, depth + 1));
	}

Google

Pergunta de entrevista da empresa Google

Respostas da entrevista

Empresas seguidas

Buscas de vagas