# 二叉树子节点的最近父节点

p、q 为不同节点且均存在于给定的二叉搜索树中。

struct Path {

int capacity; //容量

int occupy; // 实际占用量

struct TreeNode **result;// 存储的路径节点

};

void addElement(struct Path *path, struct TreeNode* node) {

if (path->occupy == path->capacity) {

// 扩容

path->capacity *= 2;

path->result = realloc(path->result, sizeof(struct TreeNode *) * path->capacity);

}

path->result[path->occupy++] = node;

}

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q){

struct Path *path_p = malloc(sizeof(struct Path));

path_p->capacity = 50;

path_p->occupy = 0;

int size = sizeof(struct TreeNode *) * path_p->capacity;

path_p->result = malloc(size);

memset(path_p->result, 0 , size);

struct TreeNode *current = root;

while(current->val != p->val) {

if (current->val > p->val) {

current = current -> left;

} else {

current = current -> right;

}

}

current = root;

struct Path *path_q = malloc(sizeof(struct Path));

path_q->capacity = 50;

path_q->occupy = 0;

size = sizeof(struct TreeNode *) * path_q->capacity;

path_q->result = malloc(size);

memset(path_q->result, 0 , size);

while(current->val != q->val) {

if (current->val > q->val) {

current = current -> left;

} else {

current = current -> right;

}

}

struct TreeNode *node = NULL;

for(int pIndex = path_p->occupy - 1; pIndex >= 0; pIndex--) {

for(int qIndex = path_q->occupy - 1; qIndex >= 0; qIndex--) {

if(path_p->result[pIndex] == path_q->result[qIndex]) {

return path_p->result[pIndex];

}

}

}

return NULL;

}

current->val > p->val && current->val > q->val,则说明p,q均在current的左子树上，此时取current = current->left;

current->val < p->val && current->val < q->val,则说明p,q均在current的右子树上，此时取current = current->right;

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {

struct TreeNode* ancestor = root;

while (true) {

if (p->val < ancestor->val && q->val < ancestor->val) {

ancestor = ancestor->left;

} else if (p->val > ancestor->val && q->val > ancestor->val) {

ancestor = ancestor->right;

} else {

return ancesto

}

}

return NULL;

}

p,q结点分布在当前结点两侧或者当前结点就是p或者q之一，那么根结点就是最近父节点；

p,q结点在当前结点的左子树上，那么最近父结点肯定是第一个查询到的p或者q；

p,q结点分布在当前结点右子树上，那么那么最近父结点肯定是第一个查询到的p或者q；

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {

if (!root) return NULL;

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

struct TreeNode *left = lowestCommonAncestor(root->left, p, q);

struct TreeNode *right = lowestCommonAncestor(root->right, p, q);

if (left && right) return root;

return left ? left : right;

}

0 条评论

• ### LeetCode 742. 二叉树最近的叶节点（建立父节点信息+BFS）

给定一个 每个结点的值互不相同 的二叉树，和一个目标值 k，找出树中与目标值 k 最近的叶结点。

• ### SQL 二叉树节点

这是一道在 HackerRank 上的 SQL 竞赛题，题目叫做“Binary Tree Nodes”，它的难度等级属于中级。

• ### 树形结构已知子节点找父节点

假如结构树如下，如何根据已经的label寻找父级label，网上找了几个比较好的方法

• ### 二叉树：删除节点

https://leetcode-cn.com/problems/delete-node-in-a-bst/

• ### LeetCode 1602. 找到二叉树中最近的右侧节点（BFS）

给定一棵二叉树的根节点 root 和树中的一个节点 u ，返回与 u 所在层中距离最近的右侧节点，当 u 是所在层中最右侧的节点，返回 null 。

• ### 在二叉树中找到一个节点的后继节点

该结构比普通二叉树节点结构多了一个指向父节点的parent指针。 假设有一 棵Node类型的节点组成的二叉树， 树中每个节点的parent指针都正确地指向自己的...

• ### 【算法】二叉树中找到一个节点的后继节点，前继节点

该结构比普通二叉树节点结构多了一个指向父节点parent指针。 假设有一 棵Node类型的节点组成的二叉树，树中每个节点的parent指针都正确地指向自己的父...

• ### 排序二叉树-删除节点

我们已经了解了什么是排序二叉树以及排序二叉树的遍历和添加元素，现在我们一起来看一下，排序二叉树是如何删除元素的。

• ### LeetCode 671. 二叉树中第二小的节点

给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。

• ### LeetCode222. 完全二叉树的节点个数

常规思路，遍历整棵树，时间复杂度O(N)，但是有一种时间复杂度小于O(N)的做法  首先遍历头结点右子树的最左边界，如果最左边界不为空，说明头结点的左子...

• ### Leetcode 993. 二叉树的堂兄弟节点

在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。

• ### leetCode161|完全二叉树的节点个数

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h...