Google Interview Question
SDE1sCountry: United States
public static List<List<Integer>> getLongestPath(TreeNode root) {
List<List<Integer>> results = new LinkedList<List<Integer>>();
if (root == null)
return results;
TreeNode maxNode = root;
Integer maxDist = new Integer(0);
Hashtable<TreeNode, Integer> nodes = new Hashtable<TreeNode, Integer>();
// calculate longest path to child(s) for all nodes and
// find a node that has max sum of longest paths to its left and right child nodes
getMaxDepth(root, maxNode, maxDist, nodes);
// get all possible paths to farest nodes from left and right
LinkedList<LinkedList<TreeNode>> leftPaths = new LinkedList<LinkedList<TreeNode>>();
LinkedList<LinkedList<TreeNode>> rightPaths = new LinkedList<LinkedList<TreeNode>>();
if (maxNode.left != null)
pathsToDeepest(maxNode.left, true, new LinkedList<TreeNode>(), leftPaths, nodes);
else
leftPaths.add(new LinkedList<TreeNode>());
if (maxNode.right != null)
pathsToDeepest(maxNode.right, false, new LinkedList<TreeNode>(), rightPaths, nodes);
else
rightPaths.add(new LinkedList<TreeNode>());
// join left path(s), node and right path(s)
for(LinkedList<TreeNode> lp:leftPaths) {
List<Integer> list = new LinkedList<Integer>();
for(TreeNode n:lp)
list.add(n.val);
list.add(maxNode.val);
for(LinkedList<TreeNode> rp:rightPaths) {
List<Integer> inner = new LinkedList<Integer>(list);
for(TreeNode n:rp)
inner.add(n.val);
results.add(inner);
}
}
return results;
}
// find a node with longest path to its child
public static int getMaxDepth(TreeNode n, TreeNode maxNode, Integer maxDist, Hashtable<TreeNode, Integer> nodes) {
if (n == null || (n.left == null && n.right == null)) {
return 0;
}
int left = n.left == null ? 0 : getMaxDepth(n.left, maxNode, maxDist, nodes) + 1;
int right = n.right == null ? 0 : getMaxDepth(n.right, maxNode, maxDist, nodes) + 1;
if(maxDist < left + right) {
maxNode = n;
maxDist = left + right;
}
if (n.left != null) nodes.put(n.left, left);
if (n.right != null) nodes.put(n.right, right);
return Math.max(left, right);
}
// create paths from a node to its most distance child(s)
public static void pathsToDeepest(TreeNode n, boolean addFirst, LinkedList<TreeNode> path,
LinkedList<LinkedList<TreeNode>> allPaths, Hashtable<TreeNode, Integer> nodes) {
if (n == null)
return;
int left = n.left != null ? nodes.get(n.left) : 0;
int right = n.right != null ? nodes.get(n.right) : 0;
if (addFirst)
path.addFirst(n);
else
path.add(n);
if (left == right) {
if (left != 0) {
LinkedList<TreeNode> pathC = new LinkedList<TreeNode>(path);
pathsToDeepest(n.left, addFirst, path, allPaths, nodes);
pathsToDeepest(n.right, addFirst, pathC, allPaths, nodes);
} else {
allPaths.add(path);
}
}
if (left > right)
pathsToDeepest(n.left, addFirst, path, allPaths, nodes);
if (left < right)
pathsToDeepest(n.right, addFirst, path, allPaths, nodes);
}
We can first find the nodes which have the maximum sum of heights of the left and right sub trees. After that, for each such node (top_node below), we find all longest paths in the left sub tree and in the right sub tree. Then we combine the paths to find all paths having the maximum length.
#include <iostream>
#include <vector>
using namespace std;
class Node {
public:
Node(int val)
{
val_ = val;
left_ = NULL;
right_ = NULL;
}
int val_;
Node *left_;
Node *right_;
};
int GetHeight(Node *n, int &longest_paths_len,
vector<Node *> &longest_paths_top_nodes)
{
if (!n) {
return 0;
}
int left_height = GetHeight(n->left_, longest_paths_len, longest_paths_top_nodes);
int right_height = GetHeight(n->right_, longest_paths_len, longest_paths_top_nodes);
int max_len = left_height + 1 + right_height;
if (max_len >= longest_paths_len) {
if (max_len > longest_paths_len) {
longest_paths_top_nodes.clear();
}
longest_paths_len = max_len;
longest_paths_top_nodes.push_back(n);
}
return max(left_height, right_height) + 1;
}
void FindLongestPath(Node *n, vector<Node *> &path, int &longest_paths_len,
vector<vector<Node *>> &longest_paths)
{
if (n) {
path.push_back(n);
if (path.size() >= longest_paths_len) {
if (path.size() > longest_paths_len) {
longest_paths.clear();
}
longest_paths.push_back(path);
longest_paths_len = path.size();
}
FindLongestPath(n->left_, path, longest_paths_len, longest_paths);
FindLongestPath(n->right_, path, longest_paths_len, longest_paths);
path.pop_back();
}
}
vector<vector<Node *>> FindLongestPaths(Node *root)
{
vector<Node *> longest_paths_top_nodes;
int longest_paths_len = 0;
GetHeight(root, longest_paths_len, longest_paths_top_nodes);
vector<vector<Node *>> longest_paths;
for (Node *top_node : longest_paths_top_nodes) {
int longest_paths_len = 0;
vector<Node *> path;
vector<vector<Node *>> left_longest_paths;
FindLongestPath(top_node->left_, path, longest_paths_len, left_longest_paths);
longest_paths_len = 0;
path.clear();
vector<vector<Node *>> right_longest_paths;
FindLongestPath(top_node->right_, path, longest_paths_len, right_longest_paths);
if (left_longest_paths.empty()) {
left_longest_paths.push_back(vector<Node *>());
}
if (right_longest_paths.empty()) {
right_longest_paths.push_back(vector<Node *>());
}
for (auto const &left_path : left_longest_paths) {
for (auto const &right_path : right_longest_paths) {
path.clear();
path.insert(path.end(), left_path.begin(), left_path.end());
reverse(path.begin(), path.end());
path.push_back(top_node);
path.insert(path.end(), right_path.begin(), right_path.end());
longest_paths.push_back(path);
}
}
}
return longest_paths;
}
int main()
{
Node n1(1);
Node n2(2);
Node n3(3);
Node n4(4);
Node n5(5);
n1.left_ = &n2;
n1.right_ = &n3;
n2.left_ = &n3;
n2.left_ = &n4;
n2.right_ = &n5;
vector<vector<Node *>> paths = FindLongestPaths(&n1);
for (auto const &path : paths) {
for (Node *n : path) {
cout << "->" << n->val_;
}
cout << "\n";
}
return 0;
}
Same concept as of Alex, but shorter code:
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
p = TreeNode(1)
p.left = TreeNode(2)
p.right = TreeNode(3)
p.left.left = TreeNode(4)
p.left.right = TreeNode(5)
def glp(tree, lp):
if tree is None:
return []
left = [tree.val] + glp(tree.left, lp)
right = [tree.val] + glp(tree.right, lp)
lp.append(left[::-1] + right[1:])
if len(left) > len(right):
return left
else:
return right
def getLongestPath(tree):
longest_path = []
tmp = []
glp(tree, longest_path)
print longest_path
getLongestPath(p)
share my java codes
public static List<List<Integer>> findLongestPath(TreeNode root){
List<List<Integer>> res = new ArrayList<>();
if(root==null){
return res;
}
helperFindPath(root,res);
return res;
}
public static List<List<Integer>> helperFindPath(TreeNode root,List<List<Integer>> res){
List<List<Integer>> ans = new ArrayList<>();
if(root==null){
List<Integer> list = new ArrayList<>();
ans.add(list);
return ans;
}
if(root.left==null && root.right==null){
List<Integer> temp = new ArrayList<>();
temp.add(root.val);
ans.add(temp);
return ans;
}
List<List<Integer>> left_list = helperFindPath(root.left,res);
List<List<Integer>> right_list = helperFindPath(root.right,res);
for(List<Integer> left:left_list){
for(List<Integer> right:right_list){
List<Integer> temp = new ArrayList<>();
temp.addAll(left);
temp.add(root.val);
temp.addAll(right);
if(res.size()!=0 && res.get(0).size()<temp.size()){
res.clear();
res.add(temp);
}else if(res.size()==0 || res.get(0).size()==temp.size()){
res.add(temp);
}
if(left.size()>right.size()){
List<Integer> list = new ArrayList<>();
list.add(root.val);
list.addAll(left);
ans.add(list);
}else if(left.size()<right.size()){
List<Integer> list = new ArrayList<>();
list.add(root.val);
list.addAll(right);
ans.add(list);
}else{
List<Integer> list1 = new ArrayList<>();
List<Integer> list2 = new ArrayList<>();
list1.add(root.val);
list1.addAll(left);
list2.add(root.val);
list2.addAll(right);
ans.add(list1);
ans.add(list2);
}
}
}
return ans;
}
From your example, it looks like they only care for the length of the path.
We will do following
Worst case Complexity is O(n*n) + O(nlog(n)), as we will be looking for all possible path. Although the avg case complexity would be O(n) + O(log(n)).
- sonesh May 01, 2017