1、对于二叉搜索树,里边的元素都是排好序的,那么从根节点向下搜索,找到第一个节点p满足p->data > pt1->data 且 p->data < pt2->data(假定pt1->data < pt2->data)即是满足要求的公共父节点; 节点结构: struct node{ int data; node *left, *right; }; 2、对于有指向父节点指针的二叉树,那么通过回溯找到根节点并对遍历过的节点予以保存,找到第一个相同的即是公共父节点。如果元素互异,保存元素以作比对即可,否则保存指针(地址)做比对; 这种情况下,树的节点结构应为: struct node{ int data; node *left, *right, *parent; }; 3、对于既没有排序,也没有父指针的一般情况,可以多费一些空间,将此树当作完全二叉树存入数组,那么每一个根节点与子节点的索引关系应为(k, 2k, 2k+1)当我们遍历到待查父节点的元素时记录其索引,将其索引依次除2,直到1,即全树的根节点。对于两个树同样操作,我们就能找到对应的共同父节点了。需要注意的是,我们没有必要存储所有的树节点,只需存储到包含两个待查父节点的节点即可。 节点结构: struct node{ int data; node *left, *right; };
75.二叉树两个结点的最低共同父结点 题目:二叉树的结点定义如下: struct TreeNode { int m_nvalue; TreeNode* m_pLeft; TreeNode* m_pRight; }; 输入二叉树中的两个结点,输出这两个结点在数中最低的共同父结点。 分析:求数中两个结点的最低共同结点是面试中经常出现的一个问题。这个问题至少有两个 变种。 ANSWER Have done this. Do it again for memory... TreeNode* getLCA(TreeNode* root, TreeNode* X, TreeNode *Y) { if (root == NULL) return NULL; if (X == root || Y == root) return root; TreeNode * left = getLCA(root->m_pLeft, X, Y); TreeNode * right = getLCA(root->m_pRight, X, Y); if (left == NULL) return right; else if (right == NULL) return left; else return root; } |
|