Shulou(Shulou.com)06/02 Report--

This article introduces how to find the lowest common parent of the two nodes in the python binary tree. The content is very detailed. Interested friends can use it for reference. I hope it will be helpful to you.

You must traverse to find the ancestor set of one node, and then compare the ancestor set of the two nodes to find the lowest one. Here, a post-order traversal is used and a stack is passed in to record the ancestor node of the node. Each time you visit a node, push the node onto the stack, and then determine whether the node is the one you are looking for, and if so, return. Then look for its left and right subtrees, and return when the node you want to find is in its left and right subtrees. Then determine whether the node is the same as the top node of the stack, and if so, pop up the top element of the stack. This is because the same means that no new node is added when visiting its left and right subtree, that is, if the node you are looking for is not in its left and right subtree, then the node is not the ancestor of the node you are looking for.

# include#includeusing namespace std;struct BinaryTreeNode {int _ data; BinaryTreeNode* _ left; BinaryTreeNode* _ right; BinaryTreeNode (int x): _ data (x), _ left (NULL), _ right (NULL) {}}; class BinaryTree {private: BinaryTreeNode* _ root Private: void _ Clear (BinaryTreeNode* root) {if (root = = NULL) return; _ Clear (root- > _ left); _ Clear (root- > _ right); delete root } BinaryTreeNode* _ CreateBinary (int* arr, int& index, const int size) {BinaryTreeNode* ret = NULL; if (index)

_ left = _ CreateBinary (arr, + + index, size); ret- > _ right = _ CreateBinary (arr, + + index, size);} return ret;} BinaryTreeNode* _ Find (BinaryTreeNode* root, int x) {if (root = = NULL) return NULL If (root- > _ data = = x) return root; BinaryTreeNode* leftRet = _ Find (root- > _ left, x); if (leftRet) return leftRet; BinaryTreeNode* rightRet = _ Find (root- > _ right, x); return rightRet } BinaryTreeNode* _ GetPath (BinaryTreeNode* root, const BinaryTreeNode* child1, const BinaryTreeNode* child2) {if (root = = NULL) return NULL; bool temp = isInclude (root, child1, child2); if (temp = = false) return NULL Else {BinaryTreeNode* leftFind = _ GetPath (root- > _ left, child1, child2); BinaryTreeNode* rightFind = _ GetPath (root- > _ right, child1, child2); if (leftFind = = NULL&&rightFind = = NULL) return root Else if (leftFind = = NULL&&rightFind) return rightFind; else return leftFind }} bool isInclude (BinaryTreeNode* root, const BinaryTreeNode* child1, const BinaryTreeNode* child2) {if (root = = NULL) return false; bool C1 = false, c2 = false; if (root = = child1) C1 = true If (root = = child2) c2 = true; if (c1&&c2) return true; else {if (root- > _ left, child1, child2)) return true Else if (isInclude (root- > _ right, child1, child2) return true; else return false }} bool _ GetPathStack (BinaryTreeNode* root, BinaryTreeNode* child, stack& s) {if (root = = NULL) return false; s.push (root); if (root = = child) {return true } if (_ GetPathStack (root- > _ left, child, s)) return true; if (_ GetPathStack (root- > _ right, child, s)) {return true;} s.pop (); return false } public: BinaryTree (): _ root (NULL) {} BinaryTree (int* arr, int size): _ root (NULL) {int index = 0; _ root = _ CreateBinary (arr, index, size) } ~ BinaryTree () {if (_ root = = NULL) return; _ Clear (_ root);} void PostOrder_NonR () {if (_ root = = NULL) return; stack s BinaryTreeNode* cur = _ root; BinaryTreeNode* prev = NULL; while (cur | |! s.empty ()) {while (cur) {s.push (cur) Cur = cur- > _ left;} BinaryTreeNode* top = s.top (); if (top- > _ right = = NULL | | prev&&prev = = top- > _ right) {cout _ data _ right }} cout size2) {int dif = size1-size2; while (dif--) {s1.pop () }} else {int dif = size2-size1; while (dif--) {s2.pop () }} BinaryTreeNode* top1 = NULL; BinaryTreeNode* top2 = NULL; if (! s1.empty () & &! s2.empty ()) {top1 = s1.top (); top2 = s2.top () } while (! s1.empty () & & top1! = top2) {s1.pop (); top1 = s1.top (); s2.pop (); top2 = s2.top () } return top1 = = top2? Top1: NULL;} / * BinaryTreeNode* LastCommonFather (BinaryTreeNode* child1, BinaryTreeNode* child2) {if (_ root = = NULL | | child1 = = NULL | | child2 = = NULL) return NULL; return _ GetPath (_ root, child1, child2);} * /} Int main () {int arr [] = {1,2,4,8,'#', 5,'#', 9,'#','#', 3, 6,'#','#', 7}; BinaryTree bt (arr, sizeof (arr) / sizeof (arr [0])); bt.PostOrder_NonR (); / * cout _ data

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.