leetcode236：二叉树的最近公共祖先

题目链接

leetcode

题目描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：”对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。“

C++ 代码

// 236. 二叉树的最近公共祖先
// 高频面试题 - CodeTop

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
#include <algorithm>
using namespace std;

// 二叉树结点的定义
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

const int NULL_NODE = -1000000001;

// 辅助函数：创建二叉树
TreeNode* createTree(const vector<int>& nums) {
    if (nums.empty()) return nullptr;

    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> queue;
    queue.push(root);
    int i = 1;
    while (!queue.empty() && i < nums.size()) {
        TreeNode* node = queue.front(); queue.pop();
        if (nums[i] != NULL_NODE) {
            node->left = new TreeNode(nums[i]);
            queue.push(node->left);
        }
        i ++;
        if (i < nums.size() && nums[i] != NULL_NODE) {
            node->right = new TreeNode(nums[i]);
            queue.push(node->right);
        }
        i ++;
    }

    return root;
}

// 辅助函数：层序遍历打印二叉树
void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;

    queue<TreeNode*> queue;
    queue.push(root);
    while (!queue.empty()) {
        TreeNode* node = queue.front(); queue.pop();
        cout << node->val << " ";
        if (node->left != nullptr) queue.push(node->left);
        if (node->right != nullptr) queue.push(node->right);
    }
    cout << endl;
}

// 辅助函数：释放二叉树
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

/*
    递归实现

    递归函数的定义：给该函数输入三个参数 root，p，q，它会返回一个结点。
    根据这个定义，分情况讨论：
        若 p 和 q 都不在以 root 为根的树中，则返回 null。
        若 p 和 q 都在以 root 为根的树中，则 left 和 right 一定分别是 p 和 q。
        若 p 和 q 只有一个在以 root 为根的树中，则返回该结点。
    
    时间复杂度：O(n)
        其中 n 是二叉树的结点数。
        二叉树的所有结点有且只会被访问一次，因此时间复杂度为 O(n)。
    空间复杂度：O(n)
        递归调用的栈深度取决于二叉树的高度，
        最坏情况下为一条链，此时高度为 n，因此空间复杂度为 O(n)。
*/
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr || root == p || root == q) {
            return root;
        }

        // 递归处理左子树和右子树
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left != nullptr && right != nullptr) {
            return root;
        }
        if (left == nullptr && right == nullptr) {
            return nullptr;
        }
        return left != nullptr ? left : right;
    }
};

/*
    递归实现，存储父节点

    1.从根结点开始遍历整棵二叉树，用哈希表 parent 记录每个结点的父结点指针。
    2.从 p 结点开始不断往它的祖先移动，用哈希表 visited 记录已经访问过的祖先结点。   
    3.同样，再从 q 结点开始不断往它的祖先移动，
        若祖先已经被访问过，则这是 p 和 q 的深度最深的公共祖先，即 LCA 结点。

    时间复杂度：O(n)
        其中 n 是二叉树的结点数。
        二叉树的所有结点有且只会被访问一次，从 p 和 q 结点往上经过的祖先结点个数不会超过 n。
    空间复杂度：O(n)
        递归调用栈的深度取决于二叉树的高度，最坏情况下二叉树为一条链，因此空间复杂度为 O(n)。
        哈希表存储需要 O(n) 的空间复杂度，因此总的空间复杂度为 O(n)。
*/
class Solution_2 {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        parent[root->val] = nullptr;
        dfs(root);
        while (p != nullptr) {
            visited[p->val] = true;
            p = parent[p->val];
        }
        while (q != nullptr) {
            if (visited[q->val]) return q;
            q = parent[q->val];
        }

        return nullptr;
    }

    void dfs(TreeNode* root) {
        if (root->left != nullptr) {
            parent[root->left->val] = root;
            dfs(root->left);
        }
        if (root->right != nullptr) {
            parent[root->right->val] = root;
            dfs(root->right);
        }
    }

private:
    unordered_map<int, TreeNode*> parent;
    unordered_map<int, bool> visited;
};

int main() {
    // 示例输入
    Solution solution;
    vector<int> nums = {3, 5, 1, 6, 2, 0, 8, NULL_NODE, NULL_NODE, 7, 4};

    // 创建二叉树
    TreeNode* root = createTree(nums);
    levelOrderTraversal(root);

    // 查找最近公共祖先
    TreeNode* result = solution.lowestCommonAncestor(root, root->left->left, root->right->right);
    // 打印结果
    cout << "Lowest Common Ancestor: " << result->val << endl;

    // 释放内存
    deleteTree(root);

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

// TreeNode 定义二叉树节点
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// createTree 根据层序遍历的值创建二叉树
func createTree(values []int) *TreeNode {
	if len(values) == 0 || values[0] == -1 {
		return nil
	}

	root := &TreeNode{Val: values[0]}
	queue := []*TreeNode{root}
	i := 1

	for i < len(values) {
		node := queue[0]
		queue = queue[1:]

		// 左子节点
		if i < len(values) && values[i] != -1 {
			node.Left = &TreeNode{Val: values[i]}
			queue = append(queue, node.Left)
		}
		i++

		// 右子节点
		if i < len(values) && values[i] != -1 {
			node.Right = &TreeNode{Val: values[i]}
			queue = append(queue, node.Right)
		}
		i++
	}

	return root
}

// findNode 在二叉树中查找指定值的节点
func findNode(root *TreeNode, val int) *TreeNode {
	if root == nil {
		return nil
	}
	if root.Val == val {
		return root
	}
	left := findNode(root.Left, val)
	if left != nil {
		return left
	}
	return findNode(root.Right, val)
}

/*
	递归查找：
		从根节点开始，递归查找左子树和右子树。
		如果当前节点是 p 或 q，返回当前节点。
	判断条件：
		如果左右子树都找到目标节点，则当前节点是最近公共祖先。
		如果只有一边找到目标节点，则返回找到的那一边。
	回溯：
		如果左右子树都没有找到目标节点，则返回 nil。

    时间复杂度：O(n)
        其中 n 是二叉树中节点的数量。
        每个节点最多被访问一次，因此时间复杂度为 O(n)。
    空间复杂度：O(n)
        递归调用的深度取决于树的高度。
        最坏情况下（树完全不平衡）为 O(n)，最好情况下（树完全平衡）为 O(logn)。
*/
// lowestCommonAncestor 找到两个节点的最近公共祖先
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil || root == p || root == q {
        return root
    }

    // 递归地查找左右子树
    left  := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)

    // 若左右子树都找到了目标节点，则当前节点是最近公共祖先
    if left != nil && right != nil {
        return root
    }
    // 若左右子树都找不到目标节点，则返回空
    if left == nil && right == nil {
        return nil
    }
    // 若左右子树只有一边找到了目标节点，则返回找到的那一边
    if left != nil {
        return left
    }
    return right
}

/*
    递归实现，存储父节点

    1.从根结点开始遍历整棵二叉树，用哈希表 parent 记录每个结点的父结点指针。
    2.从 p 结点开始不断往它的祖先移动，用哈希表 visited 记录已经访问过的祖先结点。   
    3.同样，再从 q 结点开始不断往它的祖先移动，
        若祖先已经被访问过，则这是 p 和 q 的深度最深的公共祖先，即 LCA 结点。

    时间复杂度：O(n)
        其中 n 是二叉树的结点数。
        二叉树的所有结点有且只会被访问一次，从 p 和 q 结点往上经过的祖先结点个数不会超过 n。
    空间复杂度：O(n)
        递归调用栈的深度取决于二叉树的高度，最坏情况下二叉树为一条链，因此空间复杂度为 O(n)。
        哈希表存储需要 O(n) 的空间复杂度，因此总的空间复杂度为 O(n)。
*/
func lowestCommonAncestor_1(root, p, q *TreeNode) *TreeNode {
    // 父节点映射
	parent := make(map[*TreeNode]*TreeNode)
    // 节点的访问标记
	visited := make(map[*TreeNode]bool)

	// 找到 p 和 q 的父节点关系
	var dfs func(*TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}

		if node.Left != nil {
			parent[node.Left] = node
			dfs(node.Left)
		}
		if node.Right != nil {
			parent[node.Right] = node
			dfs(node.Right)
		}
	}

	dfs(root)
    // 找到 p 的所有祖先节点
	for p != nil {
		visited[p] = true
		p = parent[p]
	}
	// 检查 q 的祖先节点是否在 p 的祖先节点中
	for q != nil {
		if visited[q] {
			return q
		}
		q = parent[q]
	}
	return nil
}

/*
	迭代实现

	使用一个栈 stack 来模拟递归过程，从根节点开始遍历整棵树。
	使用一个 parent 映射（map）来记录每个节点的父节点。这样可以在后续回溯祖先时使用。

	在遍历过程中，对于每个节点 node：
		如果它有左子节点，将左子节点加入栈，并将左子节点的父节点记录为当前节点。
		如果它有右子节点，将右子节点加入栈，并将右子节点的父节点记录为当前节点。
		这样，遍历结束后，parent 映射中存储了从根节点到每个节点的路径关系。
	记录 p 的所有祖先
		使用一个集合（ancestors）来记录节点 p 的所有祖先。
		从节点 p 开始，沿着 parent 映射向上回溯，直到根节点。将每个祖先节点加入集合中。
	查找 q 的祖先
		从节点 q 开始，沿着 parent 映射向上回溯。
		每次回溯时，检查当前节点是否在 p 的祖先集合中。如果找到，则该节点是 p 和 q 的最近公共祖先。
		如果回溯到根节点仍未找到，则返回 nil。
*/
func lowestCommonAncestor_2(root, p, q *TreeNode) *TreeNode {
    // 使用栈进行迭代
    stack := []*TreeNode{root}
    // 使用 map 记录每个节点的父节点
    parent := make(map[*TreeNode]*TreeNode)

    // 遍历二叉树，直到找到节点 p 和 q
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        if node.Left != nil {
            parent[node.Left] = node
            stack = append(stack, node.Left)
        }
        if node.Right != nil {
            parent[node.Right] = node
            stack = append(stack, node.Right)
        }
    }

    // 使用一个 set 记录节点 p 的所有祖先
    visited := make(map[*TreeNode]bool)
    for p != nil {
        visited[p] = true
        p = parent[p]
    }
    // 遍历节点 q 的祖先，找到第一个在 p 祖先集合中的节点
    for q != nil {
        if visited[q] {
            return q
        }
        q = parent[q]
    }
    return nil
}

func main() {
	// 测试用例
	testCases := []struct {
		values []int
		p, q   int
	}{
		{
			values: []int{3,5,1,6,2,0,8,-1,-1,7,4},
			p:      5,
			q:      1,
		},
		{
			values: []int{3,5,1,6,2,0,8,-1,-1,7,4},
			p:      5,
			q:      4,
		},
		{
			values: []int{1,2},
			p:      1,
			q:      2,
		},
	}

	for i, tc := range testCases {
		root := createTree(tc.values)
		pNode := findNode(root, tc.p)
		qNode := findNode(root, tc.q)
		fmt.Printf("Test Case %d, Input: values = %v, p = %d, q = %d\n", i+1, tc.values, tc.p, tc.q)
		
        if pNode != nil && qNode != nil {
			ancestor := lowestCommonAncestor_2(root, pNode, qNode)
			fmt.Printf("Test Case %d, Output: %d\n", i+1, ancestor.Val)
		} else {
			fmt.Printf("Test Case %d, Error: p or q not found in the tree\n", i+1)
		}
	}
}