Returns the lowest common ancestor of two nodes in a binary tree

1、 subject

Given the root node of a binary tree root, And two other nodes a and b, return a and b The lowest common ancestor of .

2、 analysis

The lowest common ancestor ： Two nodes go up , To which node , This node is the lowest common ancestor . For a node is the root , The other node is the node on its subtree , The root node is the lowest common ancestor .

Method 1 ： Traversing the binary tree , Use a hash table to record the parent node of each node , The nodes a All nodes along the way to the root node are put into a set , Then find from b Start along the way to the root node. What nodes are in the collection , Then it is the lowest common ancestor .

Method 2 ： Binary tree recursive routine .

1. The goal is ： Given a and b node , stay x For the root of this binary tree , find a and b The node that converges at the beginning . If there is no convergence , It returns null , Otherwise, return to the converged node .
2. possibility ： Did you find a node , Did you find b node .
   There are two kinds of ：
   • Convergence point and x irrelevant （x Not the lowest convergence point ）
     ① a and b Gathered on the left tree ;
     ② a and b Gathered on the right tree ;
     ③ a and b Incomplete , That is, there is only one node in the tree or there is no .
   • Convergence point and x of （x Is the lowest convergence point ）
     ① Zuoshu found a and b One of them , Right tree found another , They are x Convergence at ;
     ② x Itself is a node , Then I found it in the left tree or the right tree b node ;
     ③ x Itself is b node , Then I found it in the left tree or the right tree a node ;

In conclusion , The information to be collected from the left tree and the right tree ：（1） Did you find it in the tree a;（2） Did you find it in the tree b;（3）a and b The lowest common ancestor of convergence .

Collect the information of the left tree and the right tree , Then update the information of the current node , So that's one After the sequence traversal , Time complexity $O(n)$.

3、 Realization

C++ edition

/************************************************************************* > File Name: 040. Returns the lowest common ancestor of the two nodes of the binary tree .cpp > Author: Maureen > Mail: [email protected] > Created Time:  One  7/ 4 13:42:23 2022 ************************************************************************/

#include <iostream>
#include <ctime>
#include <unordered_map>
#include <set>
#include <vector>
using namespace std;

class TreeNode {
    
public:
    int value;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int data) : value(data) {
    }
};

// Method 1 ： Create a table to save the parent node information 
void fillParentMap(TreeNode *root, unordered_map<TreeNode*, TreeNode*> &parentMap) {
    
    if (root->left != nullptr) {
    
        parentMap[root->left] = root;
        fillParentMap(root->left, parentMap);
    }
    if (root->right != nullptr) {
    
        parentMap[root->right] = root;
        fillParentMap(root->right, parentMap);
    }
}

TreeNode *lowestAncestor1(TreeNode *root, TreeNode *o1, TreeNode *o2) {
    
    if (root == nullptr) return nullptr;

    unordered_map<TreeNode*, TreeNode*> parentMap;

    parentMap[root] = nullptr;

    fillParentMap(root, parentMap);// Save the parent node of each node 

    set<TreeNode*> o1set;
    
    TreeNode *cur = o1;
    //o1 All nodes along the way to the root node are put into o1set in 
    while (cur != nullptr) {
    
        o1set.insert(cur);
        cur = parentMap[cur];
    }

    cur = o2;
    while (!o1set.count(cur)) {
    
        cur = parentMap[cur];
    }

    return cur;
}


// Method 2 ： Binary tree recursive routine 
class Info {
    
public:
    bool existA;
    bool existB;
    TreeNode *ancestor;

    Info(bool a, bool b, TreeNode *node) : existA(a), existB(b), ancestor(node) {
    }
};


Info *process(TreeNode *x, TreeNode *a, TreeNode *b) {
    
    if (x == nullptr) {
    
        return new Info(false, false, nullptr);
    }

    Info *leftInfo = process(x->left, a, b);
    Info *rightInfo = process(x->right, a, b);

    bool existA = (x == a) || leftInfo->existA || rightInfo->existA;
    bool existB = (x == b) || leftInfo->existB || rightInfo->existB;

    TreeNode *ancestor = nullptr;
    if (leftInfo->ancestor != nullptr) {
    
        ancestor = leftInfo->ancestor;
    } else if(rightInfo->ancestor != nullptr) {
    
        ancestor = rightInfo->ancestor;
    } else {
    
        if (existA && existB) ancestor = x;
    }
    return new Info(existA, existB, ancestor);
}

TreeNode *lowestAncestor2(TreeNode *root, TreeNode *a, TreeNode *b) {
    
    return process(root, a, b)->ancestor;
}

//for test 
//for test 
TreeNode *generate(int level, int maxl, int maxv) {
    
    if (level > maxl || (rand() % 100 / (double)101) < 0.5)
        return nullptr;

    TreeNode *root = new TreeNode(rand() % maxv);
    root->left = generate(level + 1, maxl, maxv);
    root->right = generate(level + 1, maxl, maxv);

    return root;
}

TreeNode *generateRandomBST(int level, int value) {
    
    return generate(1, level, value);
}


void fillPrelist(TreeNode *root, vector<TreeNode*> &arr) {
    
    if (root == nullptr) return ;
    
    arr.push_back(root);
    fillPrelist(root->left, arr);
    fillPrelist(root->right, arr);
}

TreeNode *pickRandomOne(TreeNode *root) {
    
    if (root == nullptr) return nullptr;

    vector<TreeNode*> arr;
    fillPrelist(root, arr);
    int randInd = rand() % arr.size();

    return arr[randInd];
}


int main() {
    
    srand(time(0));
    int maxLevel = 4;
    int maxValue = 100;
    int testTimes = 1000001;
    
    cout << "Test begin:" << endl;
    for (int i = 0; i < testTimes; i++) {
    
        TreeNode *root = generateRandomBST(maxLevel, maxValue);
        TreeNode *a = pickRandomOne(root);
        TreeNode *b = pickRandomOne(root);
        if (lowestAncestor1(root, a, b) != lowestAncestor2(root, a, b)) {
    
            cout << "Failed!" << endl;
            return 0;
        } 
        if (i && i % 1000 == 0) cout << i << " cases passed!" << endl;
    }

    cout << "Success!!" << endl;
    return 0;
}

Java edition

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class LowestAncestor{
    
    public static class Node {
    
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
    
			this.value = data;
		}
	}

    // Method 1 ： Build table , Save parent node information 
    public static Node lowestAncestor1(Node head, Node o1, Node o2) {
    
		if (head == null) {
    
			return null;
		}
		// key The parent of is value
		HashMap<Node, Node> parentMap = new HashMap<>();
		parentMap.put(head, null);
		fillParentMap(head, parentMap);
		HashSet<Node> o1Set = new HashSet<>();
		Node cur = o1;
		o1Set.add(cur);
		while (parentMap.get(cur) != null) {
    
			cur = parentMap.get(cur);
			o1Set.add(cur);
		}
		cur = o2;
		while (!o1Set.contains(cur)) {
    
			cur = parentMap.get(cur);
		}
		return cur;
	}

    public static void fillParentMap(Node head, HashMap<Node, Node> parentMap) {
    
		if (head.left != null) {
    
			parentMap.put(head.left, head);
			fillParentMap(head.left, parentMap);
		}
		if (head.right != null) {
    
			parentMap.put(head.right, head);
			fillParentMap(head.right, parentMap);
		}
	}

    // Method 2 ： Binary tree recursive routine 
    public static Node lowestAncestor2(Node head, Node a, Node b) {
    
        return process(head, a, b).ans;
    }

    public static class Info {
    
        public boolean findA; // Whether to find a
        public boolean findB; // Whether to find b
        public Node ans; // Find the convergence point 

        public Info(boolean fa, boolean fb, Node an) {
    
            findA = fa;
            findB = fb;
            ans = an;
        }
    }

    public static Info process(Node x, Node a, Node b) {
    
        if (x == null) {
     // Set empty tree 
            return new Info(false, false, null);
        }

        Info leftInfo = process(x.left, a, b);
        Info rightInfo = process(x.right, a, b);

        // Find out a and b
        boolean findA = (x == a) || leftInfo.findA || rightInfo.findA;
        boolean findB = (x == b) || leftInfo.findB || rightInfo.findB;

        Node ans = null;
        if (leftInfo.ans != null) {
     // Find the initial convergence point on the left tree 
            ans = leftInfo.ans;
        } else if (rightInfo.ans != null) {
     // Find the initial convergence point on the right tree 
            ans = rightInfo.ans;
        } else {
     // Neither the left tree nor the right tree can find the convergence point 
            if (findA && findB) {
     // If you find out a and b, Then the convergence point must be x
                ans = x;
            }
        }
        return new Info(findA, findB, ans);
    }

    // for test
	public static Node generateRandomBST(int maxLevel, int maxValue) {
    
		return generate(1, maxLevel, maxValue);
	}

	// for test
	public static Node generate(int level, int maxLevel, int maxValue) {
    
		if (level > maxLevel || Math.random() < 0.5) {
    
			return null;
		}
		Node head = new Node((int) (Math.random() * maxValue));
		head.left = generate(level + 1, maxLevel, maxValue);
		head.right = generate(level + 1, maxLevel, maxValue);
		return head;
	}

	// for test
	public static Node pickRandomOne(Node head) {
    
		if (head == null) {
    
			return null;
		}
		ArrayList<Node> arr = new ArrayList<>();
		fillPrelist(head, arr);
		int randomIndex = (int) (Math.random() * arr.size());
		return arr.get(randomIndex);
	}

	// for test
	public static void fillPrelist(Node head, ArrayList<Node> arr) {
    
		if (head == null) {
    
			return;
		}
		arr.add(head);
		fillPrelist(head.left, arr);
		fillPrelist(head.right, arr);
	}

	public static void main(String[] args) {
    
		int maxLevel = 4;
		int maxValue = 100;
		int testTimes = 1000000;
		for (int i = 0; i < testTimes; i++) {
    
			Node head = generateRandomBST(maxLevel, maxValue);
			Node o1 = pickRandomOne(head);
			Node o2 = pickRandomOne(head);
			if (lowestAncestor1(head, o1, o2) != lowestAncestor2(head, o1, o2)) {
    
				System.out.println("Oops!");
			}
		}
		System.out.println("finish!");
	}
}