個(gè)人中心
退出
劍指offer之求二叉樹中兩個(gè)節(jié)點(diǎn)的最低共同父節(jié)點(diǎn)
1 問題
求二叉樹中倆個(gè)節(jié)點(diǎn)的最低共同父節(jié)點(diǎn)，比如二叉樹如下
4
2 6
1 3 5 7
比如節(jié)點(diǎn)1和3兩個(gè)節(jié)點(diǎn)的最低共同父節(jié)點(diǎn)是2，節(jié)點(diǎn)3和5兩個(gè)節(jié)點(diǎn)的最低共同父節(jié)點(diǎn)是4,節(jié)點(diǎn)5和6兩個(gè)節(jié)點(diǎn)的最低共同父節(jié)點(diǎn)是6,
也有可能其中1個(gè)節(jié)點(diǎn)或者2個(gè)節(jié)點(diǎn)不在二叉樹里面，那么他們就沒有最低共同父節(jié)點(diǎn)。
2 分析
4
2 6
1 3 5 7
比如我們求節(jié)點(diǎn)1和3兩個(gè)節(jié)點(diǎn)的最低共同父節(jié)點(diǎn)，我們保存每個(gè)根節(jié)點(diǎn)到該節(jié)點(diǎn)的最短路徑節(jié)點(diǎn)值，比如節(jié)點(diǎn)1的路徑就是4->2->1 然后節(jié)點(diǎn)3的路徑是4->2->3,然后我們再把這個(gè)保存的2個(gè)路徑依次從尾巴進(jìn)行進(jìn)行比較，然后就能獲取兩個(gè)節(jié)點(diǎn)的最低共同父節(jié)點(diǎn)值。
3 代碼實(shí)現(xiàn)
#include <iostream>
#include <vector>
#include <stdlib.h>
using namespace std;
typedef struct Tree
{
int value;
struct Tree* left;
struct Tree* right;
Tree(int value) : value(value), left(NULL), right(NULL) {}
} Tree;
class CommonParentNode
{
public:
bool hasPath(Tree* head, Tree* node, std::vector<Tree *>& vector)
{
if (head == NULL)
return false;
///先把我們的遍歷節(jié)點(diǎn)保存到vector里面去
vector.push_back(head);
if (head == node)
return true;
//如果這樣寫只能說明子遞歸return值了，但是這個(gè)函數(shù)沒有返回值。
if (head->left != NULL && hasPath(head->left, node, vector))
return true;
if (head->right != NULL && hasPath(head->right, node, vector))
return true;
//這里一定要調(diào)用pop_back函數(shù)，如果這個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)都為空或者左子樹或者右子樹里面不包含這個(gè)我們的節(jié)點(diǎn)，
//這個(gè)節(jié)點(diǎn)就要彈出來，如果沒有這個(gè)函數(shù)，那么我們的vector里面保存的先序遍歷到這個(gè)節(jié)點(diǎn)的所有節(jié)點(diǎn)值，
//而不是根節(jié)點(diǎn)到這個(gè)節(jié)點(diǎn)的最短距離。
vector.pop_back();
return false;
}
Tree* getCommmonParent(Tree* node, Tree* node1, Tree* node2)
{
if (node == NULL || node1 == NULL || node2 == NULL)
{
std::cout << "node == NULL || node1 == NULL || node2 == NULL" << std::endl;
return NULL;
}
vector<Tree *> vector1;
vector<Tree *> vector2;
bool result1 = hasPath(node, node1, vector1);
if (!result1)
return NULL;
bool result2 = hasPath(node, node2, vector2);
if (!result2)
return NULL;
//我們vector依次保存的是從頭結(jié)點(diǎn)到該節(jié)點(diǎn)的路徑，我們遍歷的時(shí)候應(yīng)該從vector的尾巴開始遍歷,注釋的遍歷錯(cuò)了，要注意
// for (int i = 0; i < vector1.size(); ++i)
// {
// for (int j = 0; j < vector2.size(); ++j)
// {
// //if (vector1[i]->value == vector2[j]->value)
// if (vector1[i] == vector2[j])
// {
// std::cout << "common parent node value is" << vector1[i]->value << std::endl;
// return vector1[i];
// }
// }
// }
for (int i = vector1.size() - 1; i >= 0; --i)
{
for (int j = vector2.size() - 1; j >= 0; --j)
{
//if (vector1[i]->value == vector2[j]->value)
if (vector1[i] == vector2[j])
{
return vector1[i];
}
}
}
return NULL;
}
};
int main() {
Tree *node1 , *node2 , *node3, *node4, *node5, *node6, *node7, *node8;
node1 = (Tree *)malloc(sizeof(Tree));
node2 = (Tree *)malloc(sizeof(Tree));
node3 = (Tree *)malloc(sizeof(Tree));
node4 = (Tree *)malloc(sizeof(Tree));
node5 = (Tree *)malloc(sizeof(Tree));
node6 = (Tree *)malloc(sizeof(Tree));
node7 = (Tree *)malloc(sizeof(Tree));
node8 = (Tree *)malloc(sizeof(Tree));
node1->value = 4;
node2->value = 2;
node3->value = 6;
node4->value = 1;
node5->value = 3;
node6->value = 5;
node7->value = 7;
node8->value = 8;
node1->left = node2;
node1->right = node3;
node2->left = node4;
node2->right = node5;
node3->left = node6;
node3->right = node7;
node4->left = NULL;
node4->right = NULL;
node5->left = NULL;
node5->right = NULL;
node6->left = NULL;
node6->right = NULL;
node7->left = NULL;
node7->right = NULL;
/***
4
2 6
1 3 5 7
**/
CommonParentNode commonParentNode;
Tree *commonTreeNode = NULL;
commonTreeNode = commonParentNode.getCommmonParent(node1, node5, node7);
if (!commonTreeNode)
{
std::cout << "the two node do not find commonTreeNode" << std::endl;
return -1;
}
std::cout << "commonTreeNode parent node value is " << commonTreeNode->value << std::endl;
return 0;
}
4 運(yùn)行結(jié)果
commonTreeNode parent node value is 4
5 總結(jié)
這個(gè)題目的思路是保存根節(jié)點(diǎn)到每個(gè)節(jié)點(diǎn)中途最短路徑父節(jié)點(diǎn)值，然后進(jìn)行比較，同時(shí)我們應(yīng)該可以知道求根節(jié)點(diǎn)到該節(jié)點(diǎn)最短路徑的每個(gè)節(jié)點(diǎn)值，就是vector里面保存的每個(gè)節(jié)點(diǎn)，同時(shí)也知道根節(jié)點(diǎn)到該節(jié)點(diǎn)的高度值，也就是這個(gè)vecter里面保存數(shù)據(jù)的大小，既vector.size()函數(shù)的值，代碼和上面部分代碼一樣。
bool hasPath(Tree* head, Tree* node, std::vector<Tree *>& vector)
{
if (head == NULL)
return false;
///先把我們的遍歷節(jié)點(diǎn)保存到vector里面去
vector.push_back(head);
if (head == node)
return true;
//如果這樣寫只能說明子遞歸return值了，但是這個(gè)函數(shù)沒有返回值。
if (head->left != NULL && hasPath(head->left, node, vector))
return true;
if (head->right != NULL && hasPath(head->right, node, vector))
return true;
//這里一定要調(diào)用pop_back函數(shù)，如果這個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)都為空或者左子樹或者右子樹里面不包含這個(gè)我們的節(jié)點(diǎn)，
//這個(gè)節(jié)點(diǎn)就要彈出來，如果沒有這個(gè)函數(shù)，那么我們的vector里面保存的先序遍歷到這個(gè)節(jié)點(diǎn)的所有節(jié)點(diǎn)值，
//而不是根節(jié)點(diǎn)到這個(gè)節(jié)點(diǎn)的最短距離。
vector.pop_back();
return false;
}
很經(jīng)典的代碼。
作者：chen.yu
深信服三年半工作經(jīng)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號(hào)：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)
分類導(dǎo)航