返回二叉树中两个节点的最低公共祖先

1、题目

给定一棵二叉树的根节点 root，和另外两个节点 a 和 b，返回 a 和 b 的最低公共祖先。

2、分析

最低公共祖先：两个节点往上走，到哪个节点汇聚，该节点就是最低公共祖先。对于一个节点是根，另一个节点是其子树上的节点的情况，该根节点就是最低公共祖先。

方法一：遍历二叉树，利用哈希表记录每个节点的父节点，将节点 a 沿途的到根节点的所有节点都放入一个集合中，然后找到从 b 开始沿途一直到根节点有什么节点在集合中，则它就是最低公共祖先。

方法二：二叉树递归套路。

1. 目标：给定 a 和 b 节点，在 x 为根的这棵二叉树上，找到 a 和 b 最开始汇聚的节点。如果没有汇聚，则返回空，否则返回汇聚的节点。
2. 可能性：是否发现了 a 节点，是否发现了 b 节点。
   分为两类：
   • 汇聚点和 x 无关（x 不是最低汇聚点）
     ① a 和 b 在左树上汇聚了；
     ② a 和 b 在右树上汇聚了；
     ③ a 和 b 不全，即该树上只有其中一个节点或者没有。
   • 汇聚点和 x 有关（x就是最低汇聚点）
     ① 左树发现了 a 和 b 其中一个，右树发现了另一个，二者在 x 处汇聚；
     ② x 本身就是 a 节点，然后在左树或者右树发现了 b 节点；
     ③ x 本身就是 b 节点，然后在左树或者右树发现了 a 节点；

总结来说，向左树和右树需要搜集的信息：（1）在树上是否发现了 a；（2）在树上是否发现了 b；（3）a 和 b 汇聚的最低公共祖先。

收集左树和右树的信息，然后更新当前节点的信息，这就是一个后序遍历，时间复杂度$O(n)$。

3、实现

C++ 版

/************************************************************************* > File Name: 040.返回二叉树两个节点的最低公共祖先.cpp > Author: Maureen > Mail: [email protected] > Created Time: 一 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) {
    }
};

//方法一：建表保存父节点信息
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);//保存每个节点的父节点

    set<TreeNode*> o1set;
    
    TreeNode *cur = o1;
    //o1节点沿途到根节点的所有节点放入o1set中
    while (cur != nullptr) {
    
        o1set.insert(cur);
        cur = parentMap[cur];
    }

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

    return cur;
}


//方法二：二叉树递归套路
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 版

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;
		}
	}

    //方法一：建表，保存父节点信息
    public static Node lowestAncestor1(Node head, Node o1, Node o2) {
    
		if (head == null) {
    
			return null;
		}
		// key的父节点是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);
		}
	}

    //方法二：二叉树递归套路
    public static Node lowestAncestor2(Node head, Node a, Node b) {
    
        return process(head, a, b).ans;
    }

    public static class Info {
    
        public boolean findA; //是否找到a
        public boolean findB; //是否找到b
        public Node ans; //是否找到汇聚点

        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) {
     //设置空树
            return new Info(false, false, null);
        }

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

        //发现a和b
        boolean findA = (x == a) || leftInfo.findA || rightInfo.findA;
        boolean findB = (x == b) || leftInfo.findB || rightInfo.findB;

        Node ans = null;
        if (leftInfo.ans != null) {
     //左树上找到最初汇聚点
            ans = leftInfo.ans;
        } else if (rightInfo.ans != null) {
     //右树上找到最初汇聚点
            ans = rightInfo.ans;
        } else {
     //左树和右树都没有找到汇聚点
            if (findA && findB) {
     //如果发现了a和b，那么汇聚点一定就是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!");
	}
}