最近公共祖先

 

描述

ENG

给定一棵二叉树，找到两个节点的最近公共父节点(LCA)。

最近公共祖先是两个节点的公共的祖先节点且具有最大深度。

 

假设给出的两个节点都在树中存在

样例

样例 1:

输入：{1},1,1

输出：1

解释：

 二叉树如下（只有一个节点）:

         1

 LCA(1,1) = 1

样例 2:

输入：{4,3,7,#,#,5,6},3,5

输出：4

解释：

 二叉树如下:

 

      4

     / \

    3   7

       / \

      5   6

                    

 LCA(3, 5) = 4

思路：从根节点开始遍历，如果p和q中的任一个和root匹配，那么root就是最低公共祖先。 如果都不匹配，则分别递归左、右子树，如果有一个 节点出现在左子树，并且另一个节点出现在右子树，则root就是最低公共祖先. 如果两个节点都出现在左子树，则说明最低公共祖先在左子树中，否则在右子树。

#include <stdio.h> #include <stdlib.h>

/**  *  * Definition for a binary tree node.  */ struct btree {     int val;     struct btree *left;     struct btree *right; };

struct btree *lowest_common_ancestor(struct btree *root, struct btree *p, struct btree *q) {     struct btree *left = NULL;     struct btree *right = NULL;

    if (root == NULL) {         return NULL;     }

    if (root->val == p->val || root->val == q->val) {         return root;     }

    left = lowest_common_ancestor(root->left, p, q);     right = lowest_common_ancestor(root->right, p, q);     if (left != NULL && right != NULL) {         return root;     }

    if (left == NULL) {         return right;     }

    return left; }

//preorder create binary tree struct btree *create_btree(int **data) {     struct btree *root = NULL;     int *p = *data;     int i;

    if(*p == 0xFF) {         return NULL;     } else {         root = (struct btree *)malloc(sizeof(struct btree));

        root->val = *p;         p = ++(*data);         root->left = create_btree(data);         p = ++(*data);         root->right = create_btree(data);

        return root;     } }

//preorder parse binary tree void parse_btree(struct btree *tree) {     if (tree == NULL) {         printf("0xFF ");         return;     } else {         printf("%d ", tree->val);         parse_btree(tree->left);         parse_btree(tree->right);     } }

void find_node(struct btree *tree, int val, struct btree **result) {     if (tree == NULL) {         return;     } else {         if (val == tree->val) {             *result = tree;             return;         }         find_node(tree->left, val, result);         find_node(tree->right, val, result);     } }

int main() {     struct btree *tree = NULL;     int data[13] = {35, 13, 0, 0xFF, 0xFF, -15, 0xFF, 19, 0xFF, 0xFF, -7, 0xFF, 0xFF};     int *p = data;     int i;     struct btree *t1 = NULL, *t2 = NULL, *result = NULL;

    for (i=0; i<13; i++) {         if (data[i] == 0xFF)             printf("0x%X ", data[i]);         else             printf("%d ", data[i]);     }

    printf("\n");     tree = create_btree(&p);     printf("\n");     parse_btree(tree);     printf("\n");     find_node(tree, -15, &t1);     if (t1)         printf("%d, t1:%p\n", t1->val, t1);     find_node(tree, 19, &t2);     if (t2)        printf("%d, t2:%p\n", t2->val, t2);

    result = lowest_common_ancestor(tree, t1, t2);     if (result)        printf("%d, result:%p\n", result->val, result); }