【算法与数据结构】236、LeetCode二叉树的最近公共祖先

文章目录

一、题目
二、解法
三、完整代码

所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

在这里插入图片描述

二、解法

思路分析：根据定义，最近祖先节点需要遍历节点的左右子树，然后才能知道是否为最近祖先节点。那么这种需求是先遍历左右节点，然后遍历中间节点，属于左右中的后序遍历模式。因此在程序当中，我们选择递归中序遍历。输入参数为根节点p q节点。终止条件是当前节点和p q当中任意一个节点相等时就返回，遍历到空节点也返回。因为是后序遍历，根据遍历完左右子树后的返回值确定返回参数，如果返回值都不为空，则当前节点就是最近祖先节点。如果left为空，right不为空，则最近祖先节点在右子树，反之亦然。均为空则返回NULL。
程序如下：

class Solution2 {
public:
    // 后序遍历: 左右中
    // 1、输入参数
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 2、终止条件
        if (root == q || root == p || root == NULL) return root;    // 如果节点相等或者是空节点返回

        // 3、单层递归逻辑
        TreeNode* left = lowestCommonAncestor(root->left, p, q);        // 左
        TreeNode* right = lowestCommonAncestor(root->right, p, q);      // 右

        // 1、返回值
        if (left != NULL && right != NULL) return root;
        if (left == NULL && right != NULL) return right;
        else if (left != NULL && right == NULL) return left;
        else { //  (left == NULL && right == NULL)
            return NULL;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

代码优化：

class Solution {
public:
    // 后序遍历: 左右中
    // 1、输入参数
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 2、终止条件
        if (root == p || root == q || root == NULL) return root;    // 如果节点相等或者是空节点返回

        // 3、单层递归逻辑
        TreeNode* left = lowestCommonAncestor(root->left, p, q);        // 左
        TreeNode* right = lowestCommonAncestor(root->right, p, q);      // 右
        if (left != NULL && right != NULL) return root;
        if (left == NULL) return right;

        // 1、返回值
        return left;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

三、完整代码

# include 
# include 
# include 
# include 
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) {}
};

class Solution {
public:
    // 后序遍历: 左右中
    // 1、输入参数
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 2、终止条件
        if (root == p || root == q || root == NULL) return root;    // 如果节点相等或者是空节点返回

        // 3、单层递归逻辑
        TreeNode* left = lowestCommonAncestor(root->left, p, q);        // 左
        TreeNode* right = lowestCommonAncestor(root->right, p, q);      // 右
        if (left != NULL && right != NULL) return root;
        if (left == NULL) return right;

        // 1、返回值
        return left;
    }
};

class Solution2 {
public:
    // 后序遍历: 左右中
    // 1、输入参数
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 2、终止条件
        if (root == q || root == p || root == NULL) return root;    // 如果节点相等或者是空节点返回

        // 3、单层递归逻辑
        TreeNode* left = lowestCommonAncestor(root->left, p, q);        // 左
        TreeNode* right = lowestCommonAncestor(root->right, p, q);      // 右

        // 1、返回值
        if (left != NULL && right != NULL) return root;
        if (left == NULL && right != NULL) return right;
        else if (left != NULL && right == NULL) return left;
        else { //  (left == NULL && right == NULL)
            return NULL;
        }
    }
};

// 前序遍历迭代法创建二叉树，每次迭代将容器首元素弹出（弹出代码还可以再优化）
void Tree_Generator(vector<string>& t, TreeNode*& node) {
    if (!t.size() || t[0] == "NULL") return;    // 退出条件
    else {
        node = new TreeNode(stoi(t[0].c_str()));    // 中
        if (t.size()) {
            t.assign(t.begin() + 1, t.end());
            Tree_Generator(t, node->left);              // 左
        }
        if (t.size()) {
            t.assign(t.begin() + 1, t.end());
            Tree_Generator(t, node->right);             // 右
        }
    }
}

template<typename T>
void my_print(T& v, const string msg)
{
    cout << msg << endl;
    for (class T::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << ' ';
    }
    cout << endl;
}

template<class T1, class T2>
void my_print2(T1& v, const string str) {
    cout << str << endl;
    for (class T1::iterator vit = v.begin(); vit < v.end(); ++vit) {
        for (class T2::iterator it = (*vit).begin(); it < (*vit).end(); ++it) {
            cout << *it << ' ';
        }
        cout << endl;
    }
}

// 层序遍历
vector<vector<int>> levelOrder(TreeNode* root) {
    queue<TreeNode*> que;
    if (root != NULL) que.push(root);
    vector<vector<int>> result;
    while (!que.empty()) {
        int size = que.size();  // size必须固定, que.size()是不断变化的
        vector<int> vec;
        for (int i = 0; i < size; ++i) {
            TreeNode* node = que.front();
            que.pop();
            vec.push_back(node->val);
            if (node->left) que.push(node->left);
            if (node->right) que.push(node->right);
        }
        result.push_back(vec);
    }
    return result;
}

// 前序遍历,找二叉树中指定的键值
TreeNode* traversal_preOrder(TreeNode* cur, int val) {
    if (cur == NULL) return NULL;
    if (cur->val == val) return cur;        // 中
    if (traversal_preOrder(cur->left, val) != NULL) return traversal_preOrder(cur->left, val);        // 左   
    if (traversal_preOrder(cur->right, val) != NULL) return traversal_preOrder(cur->right, val);     // 右  
    return NULL;
}

int main()
{
    // 构建二叉树
    vector<string> t = { "3", "5", "6", "NULL", "NULL", "2", "7", "NULL", "NULL", "4", "NULL", "NULL", "1", "0", "NULL", "NULL", "8", "NULL", "NULL"};   // 前序遍历
    my_print(t, "目标树");
    TreeNode* root = new TreeNode();
    Tree_Generator(t, root);
    vector<vector<int>> tree = levelOrder(root);
    my_print2<vector<vector<int>>, vector<int>>(tree, "目标树:");

    // 构建p, q节点
    int p = 5, q = 1;
    TreeNode* P_node = traversal_preOrder(root, p);
    TreeNode* Q_node = traversal_preOrder(root, q);

    // 找最近公共祖先节点
    Solution s;
    TreeNode* result = s.lowestCommonAncestor(root, P_node, Q_node);
    cout << "节点 " << P_node->val << " 和节点 " << Q_node->val << " 的最近公共祖先节点为 " << result->val << endl;

    system("pause");
    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

end

相关阅读:
原子类在多线程编程中的重要性
 社区系统项目复盘-3
git介绍和安装、（git，github，gitlab，gitee介绍）、git工作流程、git常用命令、git忽略文件
 如何在ADS中综合耦合矩阵
 从实战出发，深入解读Netty底层核心源码，不得不说大佬就是大佬
 【uniapp小程序】视图容器cover-view
HDU 1114：Piggy-Bank ← 完全背包问题
 零基础html学习/刷题-第二期
 关于I/O——内存与CPU与磁盘之间的关系
 简单网页制作代码 HTML+CSS+JavaScript香港美食(8页)
原文地址：https://blog.csdn.net/qq_45765437/article/details/132802425