MrainW's Home

All things come to those who wait!

0%

Posted on In ,
Symbols count in article: 1.1k Reading time ≈ 1 mins.

Question

Given the root of a binary tree and an array of TreeNode objects nodes, return the lowest common ancestor (LCA) of all the nodes in nodes. All the nodes will exist in the tree, and all values of the tree’s nodes are unique.

Extending the definition of LCA on Wikipedia: “The lowest common ancestor of n nodes p1, p2, …, pn in a binary tree T is the lowest node that has every pi as a descendant (where we allow a node to be a descendant of itself) for every valid i“. A descendant of a node x is a node y that is on the path from node x to some leaf node.

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iv/

Solution

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
        Set<Integer> set = new HashSet<>();
        for (TreeNode t : nodes) set.add(t.val);
        return dfs(root, set);
    }
    private TreeNode dfs(TreeNode root, Set<Integer> set){
        if (root == null) return null;
        if (set.contains(root.val)) return root;
        TreeNode left = dfs(root.left, set);
        TreeNode right = dfs(root. right, set);
        if (left != null && right != null) return root;
        if (left != null) return left;
        if (right != null) return right;
        return null;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 1.3k Reading time ≈ 1 mins.

Question

Given the root of a binary tree, return the lowest common ancestor (LCA) of two given nodes, p and q. If either node p or q does not exist in the tree, return null. All values of the nodes in the tree are unique.

According to the definition of LCA on Wikipedia: “The lowest common ancestor of two nodes p and q in a binary tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself)”. A descendant of a node x is a node y that is on the path from node x to some leaf node.

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-ii/

Solution

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode pNode = dfs(root, p.val), qNode = dfs(root, q.val);
        return (qNode == null || pNode == null) ? null : lca(root, pNode, qNode);
    }
    private TreeNode dfs(TreeNode cur, int target){
        if (cur == null) return null;
        if (cur.val == target) return cur;
        TreeNode left = dfs(cur.left, target);
        TreeNode right = dfs(cur.right, target);
        return left == null ? right : left;
    }
    public TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lca(root.left, p, q);
        TreeNode right = lca(root.right, p, q);
        if (left != null && right != null) return root;
        if (left != null) return left;
        if (right != null) return right;
        return null;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 1k Reading time ≈ 1 mins.

Question

Given two nodes of a binary tree p and q, return their lowest common ancestor (LCA).

Each node will have a reference to its parent node. The definition for Node is below:

1
2
3
4
5
6
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

According to the definition of LCA on Wikipedia: “The lowest common ancestor of two nodes p and q in a tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself).”

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iii/

Solution

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    /*
    public Node lowestCommonAncestor(Node p, Node q) {
        Set<Node> set = new HashSet<>();
        while(true){
            if (p != null && !set.add(p)) return p;
            if (q != null && !set.add(q)) return q;
            if (p != null) p = p.parent;
            if (q != null) q = q.parent;
        }
        
    }
    Time complexity: O(n)

	Space complexity: O(n)
    */
    public Node lowestCommonAncestor(Node p, Node q){
        Node a = p, b = q;
        while (a != b){
            a = a == null ? q : a.parent;
            b = b == null ? p : b.parent;
        }
        return a;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(1)

Posted on In ,
Symbols count in article: 703 Reading time ≈ 1 mins.

Question

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

Solution

  • Solution1 
1
2
3
4
5
6
7
8
9
class Solution {
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {    
    if (root == null || root == p || root == q) return root;
    TreeNode l = lowestCommonAncestor(root.left, p, q);
    TreeNode r = lowestCommonAncestor(root.right, p, q);
    if (l == null || r == null) return l == null ? r : l;
    return root;
  }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 725 Reading time ≈ 1 mins.

Question

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

Solution

  • Solution1 
1
2
3
4
5
6
7
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
        if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
        return root;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(h)

Posted on In ,
Symbols count in article: 935 Reading time ≈ 1 mins.

Question

Given the root of a binary search tree, return a balanced binary search tree with the same node values. If there is more than one answer, return any of them.

A binary search tree is balanced if the depth of the two subtrees of every node never differs by more than 1.

https://leetcode.com/problems/balance-a-binary-search-tree/

Solution

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public TreeNode balanceBST(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(root, res);
        return bulid(0, res.size() - 1, res);
    }
    private void dfs(TreeNode root, List<Integer> res){
        if (root == null) return;
        dfs(root.left, res);
        res.add(root.val);
        dfs(root.right, res);
    }
    private TreeNode bulid(int left, int right, List<Integer> res){
        if (left > right) return null;
        int mid = left + (right - left)/ 2;
        TreeNode root = new TreeNode(res.get(mid));
        root.left = bulid(left, mid - 1, res);
        root.right = bulid(mid + 1, right, res);
        return root;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 726 Reading time ≈ 1 mins.

Question

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

Solution

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }
    public TreeNode helper(int[] nums, int start, int end){
        if(start > end) return null;
        int mid = start + (end - start)/ 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, start, mid - 1);
        root.right = helper(nums, mid + 1, end);
        return root;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(logn)

Posted on In ,
Symbols count in article: 1.3k Reading time ≈ 1 mins.

Question

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

  • BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
  • boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.
  • int next() Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.

You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.

https://leetcode.com/problems/binary-search-tree-iterator/

Solution

  • Solution1 – inorder
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class BSTIterator {
    Stack<TreeNode> stack;
    public BSTIterator(TreeNode root) {
        stack = new Stack<TreeNode>();
        pushAllLeft(root);
    }
    
    public int next() {
        TreeNode node = stack.pop();
        pushAllLeft(node.right);
        return node.val;
    }
    
    public boolean hasNext() {
        return !stack.isEmpty();
    }
    public void pushAllLeft(TreeNode root){
        while(root != null){
            stack.push(root);
            root = root.left;
        }
    }
}

Complexity:

Time complexity: O(h)

Space complexity: O(h)

Posted on In ,
Symbols count in article: 720 Reading time ≈ 1 mins.

Question

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

https://leetcode.com/problems/binary-tree-right-side-view

Solution

  • Solution1 – BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null) return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            int size = q.size();
            res.add(q.peek().val);
            for(int i = 0; i < size; i++){
                TreeNode cur = q.poll();
                if(cur.right != null) q.offer(cur.right);
                if(cur.left != null) q.offer(cur.left);
            }
        }
        return res;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 631 Reading time ≈ 1 mins.

Question

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

https://leetcode.com/problems/balanced-binary-tree/

Solution

  • Solution1 – DFS, bottom up
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }
    
    private int getHeight(TreeNode node) {
        if (node == null)
            return 0;
        int lh = getHeight(node.left), rh = getHeight(node.right);
        if (lh == -1 || rh == -1 || Math.abs(lh - rh) > 1)
            return -1;
        return 1 + Math.max(lh, rh);
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)