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: Maureen@qq.com 
	> 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;
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157

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!");
	}
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143