专栏首页正则二叉树子节点的最近父节点
原创

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

查找二叉树子节点的最近共同父节点

分析

实现

算法复杂度

其他算法

题目升级

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

实例1

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8

输出: 6

解释: 节点 2 和节点 8 的最近公共祖先是 6。

实例2

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4

输出: 2

解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。

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

分析

对于二叉树来讲,由于左右子树指针的存在,使得正常情况下的自上而下遍历显得比较简单,而下而上的查找并不那么容易,所以一种直观的思维就是从根节点开始遍历,直到找到节点p pp,记录路径数组为p a t h _ p path\_ppath_p,同理找到根节点到节点q qq的路径数组p a t h _ q path\_qpath_q,只要能够找到两个路径组中最到的i n d e x indexindex,使得p a t h _ p [ i n d e x ] = = p a t h _ q [ i n d e x ] path\_p[index]==path\_q[index]path_p[index]==path_q[index],则i n d e x indexindex对应的节点即为最近共同父节点。

实现

基于上述思考,尝试使用数组来进行路径存储。

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) {

addElement(path_p, current);

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

current = current -> left;

} else {

current = current -> right;

}

}

addElement(path_p, current);

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) {

addElement(path_q, current);

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

current = current -> left;

} else {

current = current -> right;

}

}

addElement(path_q, current);

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;

}

算法复杂度

时间复杂度:最坏的情况下,二叉搜索树变成了一个类似于链表的结构,而p , q p,qp,q是在最底端的两个节点那么搜索p , q p,qp,q节点的时间复杂度都可以达到n nn(n nn为树中节点个数),时间复杂度为O ( n ) O(n)O(n);

空间复杂度:同样最坏的情况下,需要使用开辟跟节点数相同的数组空间来存储节点路径,所以空间复杂度也为O ( n ) O(n)O(n).

其他算法

对于上述算法来讲需要遍历两次树结构来获取跟节点到指定节点的路径,然后倒叙获取路径数组中第一个相同节点即可最近父节点.但事实上,可以尝试将两次查找合并在一起,对于当前节点c u r r e n t currentcurrent,无非有三种情况:

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;

最后一种情况,要么current就是p或者q节点之一,要么p,q分别在current的左右子树上.也就是要查找的最近父节点。实现起来发给这个样子:

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;

}

这样就可以将时间复杂度降低为O ( n ) O(n)O(n),同时空间复杂度也将为常数O ( 1 ) O(1)O(1).

题目升级

如果题目中的树只是一颗普通的二叉树,那么最近父节点该怎么查找?

其实尝试将结果分类,会发现无外乎以下情况:

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;

}

同样最坏的情况是,二叉树退化成了一个类似于单链表的结构,p,q两个节点就在表的末端最后两个节点,这样的话,时间复杂度也会变为O ( n ) O(n)O(n);不消耗额外的空间。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

    Michael阿明
  • SQL 二叉树节点

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

    白日梦想家
  • LintCode-632. 二叉树的最大节点

    悠扬前奏
  • 树形结构已知子节点找父节点

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

    tianyawhl
  • 二叉树:删除节点

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

    灰子学技术
  • LeetCode 1602. 找到二叉树中最近的右侧节点(BFS)

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

    Michael阿明
  • php获取所有节点的父节点和子节点

    黄啊码
  • 在二叉树中找到一个节点的后继节点

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

    大学里的混子
  • 【算法】二叉树中找到一个节点的后继节点,前继节点

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

    MapleYe
  • leetCode176|二叉搜索树节点最小距离

    码农王同学
  • 671. 二叉树中第二小的节点

    CaesarChang张旭
  • 排序二叉树-删除节点

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

    shengjk1
  • LeetCode 366. 寻找二叉树的叶子节点(上下翻转二叉树+BFS)

    Michael阿明
  • LeetCode 671. 二叉树中第二小的节点

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

    Michael阿明
  • LeetCode222. 完全二叉树的节点个数

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

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

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

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

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

    码农王同学
  • LeetCode35|完全二叉树的节点个数

    码农王同学
  • 222. 完全二叉树的节点个数

    CaesarChang张旭

扫码关注云+社区

领取腾讯云代金券