Integer to Roman conversion - Leet Code Solution
Problem Statement Roman numerals are represented by seven different symbols: I…
August 14, 2020
First try to understand question.
You can find the location of these two nodes on the tree. There can be three possibilities:
For Case-2, on finding that both nodes are on the same side. We will repeat our same algorithm going forward in that side only.
Lets see a code for this.
public class CommonAncestor {
public static class Node {
public int data;
public Node left;
public Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
/**
* To check whether a node exists in a root element
*/
private boolean covers(Node root, Node toSearch) {
if (root == null || toSearch == null) {
return false;
}
if (root.data == toSearch.data) {
return true;
}
return this.covers(root.left, toSearch) || this.covers(root.right, toSearch);
}
private Node helper1(Node root, Node node1, Node node2) {
if (root == null) {
return null;
}
if (root.data == node1.data || root.data == node2.data) {
return root;
}
boolean firstNodeFoundOnLeft = this.covers(root.left, node1);
boolean firstNodeFoundOnRight = this.covers(root.left, node2);
if (firstNodeFoundOnLeft != firstNodeFoundOnRight) {
//both are on different sides. Found result.
return root;
}
//both are on the same side.
return this.helper1(firstNodeFoundOnLeft ? root.left : root.right,
node1, node2);
}
public Node findCommonAncestor_1(Node root, Node node1, Node node2) {
if (!this.covers(root, node1) || !this.covers(root, node2)) {
//one or both nodes are not in the tree
System.out.println("Not covered");
return null;
}
return this.helper1(root, node1, node2);
}
}
helper1(root, node1, node2)
The function calls recursively, and same code repeats.
Consider the tree to be balanced tree.
covers()
is called twice. So, its 2 times O(n)
, which computes to O(n)
helper1()
function gets called on branches one time for each node.
2 * n/2 for both nodes.
Which comes out to be: 2n/2 + 2n/4 + 2n/8 ~= O(logn)
Total complexity of this code is O(n)
Problem Statement Roman numerals are represented by seven different symbols: I…
Introduction I will list some of the interesting usage of bitwise operators…
Problem Statement Given a string, determine if it is a palindrome, considering…
Problem Statement Implement atoi which converts a string to an integer…
Problem Statement Replace all spaces in a string with ‘%20’ (three characters…
A Binary tree is a data structure which has two children nodes attached to it…
Problem Statement You are given a string text of words that are placed among…
Problem Statement You are given a rows x cols matrix grid. Initially, you are…
Problem Statement Given a string s, return the maximum number of unique…
Problem The Leetcode file system keeps a log each time some user performs a…
Problem Statement Replace all spaces in a string with ‘%20’ (three characters…
Problem Implement an algorithm to determine if a string has all the characters…