求二叉树的最低公共祖先

这个题目来讲,应该是在二叉树里面较为容易的题目了。那么如何下手呢?其实对于这样一棵二叉树来讲。

我们如何求它们的最低公共父节点呢?

假如是要你求5、6的公共父节点,那么是3.啰

为什么是3?

因为3的左子树是5,而右子树是6啰。

那么7、8的最低公共祖先呢?

1啊,因为1的左子树中有7、而1的右子树中有8啊。

那么思路来了。我们只要证明某一节点的左子树和右子树分别包含这两个节点就行了。

于是思路来了。

源代码:

注意:在本题中为了方便 ,我们传入的两个节点的值,而不是两个节的地址,呵呵,为了方便 嘛。

  1. #ifndef THELAST_COM_PARENT_H
  2. #define THELAST_COM_PARENT_H
  3. #include"reconstructBinaryTree.h"
  4. bool isInsubTree(TreeNode *node,int n_val);
  5. TreeNode *lastestCommParent(TreeNode *root,int n_val1 ,int n_val2){
  6. if(root==NULL){
  7. return NULL;
  8. }
  9. if(isInsubTree(root->left,n_val1)&&isInsubTree(root->right,n_val2)){
  10. return root;
  11. }
  12. if(isInsubTree(root->left,n_val2)&&isInsubTree(root->right,n_val1)){
  13. return root;
  14. }
  15. if(isInsubTree(root->left,n_val1)&&isInsubTree(root->left,n_val2)){
  16. return lastestCommParent(root->left,n_val1,n_val2);
  17. }
  18. if(isInsubTree(root->right,n_val1)&&isInsubTree(root->right,n_val2)){
  19. return lastestCommParent(root->right,n_val1,n_val2);
  20. }
  21. }
  22. bool isInsubTree(TreeNode *node,int n_val){
  23. if(node==NULL){
  24. return false;
  25. }
  26. if(node->val==n_val){
  27. return true;
  28. }
  29. return isInsubTree(node->left,n_val)||isInsubTree(node->right,n_val);
  30. }
  31. #endif
  1. bool isInsubTree(TreeNode *node,int n_val)
  2. 这个函数的目的是确定n_val有没有在以node为根的子树中,如果在返回为true,否则返回false.
  1. //如果n_val1和n_val2分别在左右子树中,那正好。
  2. if(isInsubTree(root->left,n_val1)&&isInsubTree(root->right,n_val2)){
  3. return root;
  4. }
  5. if(isInsubTree(root->left,n_val2)&&isInsubTree(root->right,n_val1)){
  6. return root;
  7. }
  8. //如果两个节点都在左子树中,那么往左树中走
  9. if(isInsubTree(root->left,n_val1)&&isInsubTree(root->left,n_val2)){
  10. return lastestCommParent(root->left,n_val1,n_val2);
  11. }
  12. //如果两个节点都在右子树中,那么往右子树走
  13. if(isInsubTree(root->right,n_val1)&&isInsubTree(root->right,n_val2)){
  14. return lastestCommParent(root->right,n_val1,n_val2);
  15. }

主要分析下这部分代码:

我以前也是很少关注递归的返回值的问题,我觉得这个人写得还可以,至少给我说明了这个递归返回值给程序结果带来的影响:

http://fancyseeker.com/?p=301

  1. bool isInsubTree(TreeNode *node,int n_val){
  2. if(node==NULL){
  3. return false;
  4. }
  5. if(node->val==n_val){
  6. return true;
  7. }
  8. //这里只能这么写,因为我们只要出现一个true只写了啊,也就是这个节点只要出现一次就OK了,于是用“或”
  9. //要认真考虑递归的返回值,确保下一给的结果能反馈给上一给的程序,这样一级级从上往上返回,直到第一级
  10. //第一级也就是直接影响我们整个程序返回值的。
  11. return isInsubTree(node->left,n_val)||isInsubTree(node->right,n_val);
  12. }

来自为知笔记(Wiz)

时间: 07-18

求二叉树的最低公共祖先的相关文章

编程算法 - 二叉树的最低公共祖先 代码(C)

二叉树的最低公共祖先 代码(C) 本文地址: http://blog.csdn.net/caroline_wendy 二叉树的最低公共祖先(lowest common ancestor), 首先先序遍历找到两个结点的路径, 然后依据链表路径找到最低的公共祖先. 代码: /* * main.cpp * * Created on: 2014.6.12 * Author: Spike */ /*eclipse cdt, gcc 4.8.1*/ #include <iostream> #include

二叉树求两节点最低公共祖先,求随意两节点距离

-------1.求最低公共祖先LCA( Lowest Common Ancestor ) 什么是最低公共祖先?例如以下图.2与3的LCA是1:1与4的LCA是1:4与5的LCA是2. 那么给定两个节点n1和n2,如今要找出它们的LCA,怎样找?首先分析一下,n1和n2有几种情况?第一种.n1和n2分别在一个节点的左右子树中,比方4和5,LCA就是2,5和6,LCA就是1.2和3,LCA就是1:另外一种.n1和n2都在左子树或右子树,比方2和4,LCA就是2,1和4.LCA就是1. 一共这两种情

求树中两个节点的最低公共祖先

情形1:树是搜索二叉树 思路:从树的根节点开始遍历,如果根节点的值大于其中一个节点,小于另外一个节点,则根节点就是最低公共祖先.否则如果根节点的值小于两个节点的值,则递归求根节点的右子树,如果大于两个节点的值则递归求根的左子树.如果根节点正好是其中的一个节点,那么说明这两个节点在一条路径上,所以最低公共祖先则是根节点的父节点 public static BinaryTreeNode getLowestCommonAncestor(BinaryTreeNode rootParent,BinaryT

寻找二叉树中的最低公共祖先结点----LCA(Lowest Common Ancestor )问题(递归)

转自 剑指Offer之 - 树中两个结点的最低公共祖先 题目: 求树中两个节点的最低公共祖先. 思路一: --如果是二叉树,而且是二叉搜索树,那么是可以找到公共节点的. 二叉搜索树都是排序过的,位于左子树的节点都比父节点小,而位于右子树上面的节点都比父节点大. 如果当前节点的值比两个结点 的值都大,那么最低的共同的父节点一定是在当前节点的左子树中,于是下一步遍历当前节点的左子节点. 如果当前节点的值比两个结点的值都小,那么最低的共同的父节点一定是在当前节点的右子树中,于是下一步遍历当前节点的右子

二叉树中寻找共同节点的最低公共祖先节点

问题:在一棵二叉树中,给定两个节点,求这两个节点的最低的公共祖先节点,如下图中的,节点 6 和 节点 9 的最低公共祖先节点是节点 5. 最容易联想到的是,这个问题似乎与公共子串的问题有关系,如果我们能求出两个节点到根节点的路径,再使用匹配算法得到公共的路径,取这个路径上最后一个节点,即是所求的最低公共祖先节点. 哈夫曼编码启迪了我,我打算使用 0 表示向左走,1 表示向右走.如,101 表示自根节点,走到右孩子 A,再走到 A 的左孩子 B,再走到 B 的右孩子 C .于是,根节点到节点 C

求一棵普通树的两个结点的最低公共祖先

一棵普通树,树中的结点没有指向父节点的指针,求一棵普通树的两个结点的最低公共祖先. 代码如下,我太懒没有加注释,大家自己看吧! 1 #include <iostream> 2 #include <list> 3 #include <vector> 4 using namespace std; 5 6 struct TreeNode //节点 7 { 8 char m_nValue; 9 vector<TreeNode*> m_vChildren; 10 };

树中两个结点的最低公共祖先

情况1: 树为二叉排序树. 思路:从根结点开始和输入的两个结点进行比较,如果当前结点的值比两个结点的值都大,那么最低的祖先肯定在左子树中,于是下一步遍历当前结点的左子结点.如果当前结点的值比两个结点的值都小,那么最低的祖先肯定在右子树种,于是下一步遍历当前结点的右子结点.如果当前结点正好是输入的两个结点之一,说明这两个结点有一个是另一个的祖先,这时输出当前结点的父节点即可. /* 二叉树的公共祖先系列 1.二叉树为二叉排序树 by Rowandjj 2014/8/20 */ #include<i

求解二叉查找树中的最低公共祖先结点

一,问题描述 请构造一棵二叉查找树,并给定两个结点,请找出这两个结点的最低公共祖先结点. 这里假设二叉查找树中的结点的权值存储是整型数字(见代码中的BinaryNode内部类),最低公共祖先结点如下:结点5 和 结点12 的最低公共祖先结点是结点10 二,实现思路 假设给定的两个结点的权值分别为 node1 和 node2 如果根的权值处于 node1 和 node2 之间,则根就是它们的最低公共祖先结点 如果根的权值比 node1 和 node2 都大,则它们的最低公共祖先结点在根的左子树中

Leetcode 236.二叉树的最近公共祖先

二叉树的最近公共祖先 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先. 百度百科中最近公共祖先的定义为:"对于有根树 T 的两个结点 p.q,最近公共祖先表示为一个结点 x,满足 x 是 p.q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)." 例如,给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4] 示例 1: 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1