Data Structure Binary Tree: Lowest Common Ancestor in a Binary Tree-白红宇

Data Structure Binary Tree: Lowest Common Ancestor in a Binary Tree

阅读量：5299 次

发布时间：2019-06-14

本文共 4371 字，大约阅读时间需要 14 分钟。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
             9 using namespace std;10 11 struct node {12 int data;13 struct node *left, *right;14 node() : data(0), left(NULL), right(NULL) { }15 node(int d) : data(d), left(NULL), right(NULL) { }16 };17 18 bool findpath(node *root, vector
             
               &path, int n) {19 if (!root) return false;20 path.push_back(root->data);21 if (root->data == n) return true;22 if (root->left && findpath(root->left, path, n) || root->right && findpath(root->right, path, n)) return true;23 path.pop_back();24 return false;25 }26 27 int LCA(node *root, int n1, int n2) {28 if (!root) return -1;29 vector
              
                path1, path2;30 if (!findpath(root, path1, n1) || !findpath(root, path2, n2)) return -1;31 int i = 0;32 for (; i < path1.size() && i < path2.size(); i++) {33 if (path1[i] != path2[i]) break;34 }35 return path1[i-1];36 }37 38 int main() {39 node *root = new node(1);40 root->left = new node(2);41 root->right = new node(3);42 root->left->left = new node(4);43 root->left->right = new node(5);44 root->right->left = new node(6);45 root->right->right = new node(7);46 cout << "LCA(4, 5) is " << LCA(root, 4, 5) << endl;47 cout << "LCA(4, 6) is " << LCA(root, 4, 6) << endl;48 cout << "LCA(3, 4) is " << LCA(root, 3, 4) << endl;49 cout << "LCA(2, 4) is " << LCA(root, 2, 4) << endl;50 return 0;51 }

one traversal

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
             9 using namespace std;10 11 struct node {12 int data;13 struct node *left, *right;14 node() : data(0), left(NULL), right(NULL) { }15 node(int d) : data(d), left(NULL), right(NULL) { }16 };17 18 node* LCA(node *root, int n1, int n2) {19 if (!root) return NULL;20 if (root->data == n1 || root->data == n2) return root;21 node *l = LCA(root->left, n1, n2);22 node *r = LCA(root->right, n1, n2);23 if (l && r) return root;24 return l? l : r;25 }26 27 int main() {28 node *root = new node(1);29 root->left = new node(2);30 root->right = new node(3);31 root->left->left = new node(4);32 root->left->right = new node(5);33 root->right->left = new node(6);34 root->right->right = new node(7);35 cout << "LCA(4, 5) is " << LCA(root, 4, 5)->data << endl;36 cout << "LCA(4, 6) is " << LCA(root, 4, 6)->data << endl;37 cout << "LCA(3, 4) is " << LCA(root, 3, 4)->data << endl;38 cout << "LCA(2, 4) is " << LCA(root, 2, 4)->data << endl;39 return 0;40 }

上面这段代码有些问题，当n1或者n2不存在时应该回NULL，但是回的是n1或者n2

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
             9 using namespace std;10 11 struct node {12 int data;13 struct node *left, *right;14 node() : data(0), left(NULL), right(NULL) { }15 node(int d) : data(d), left(NULL), right(NULL) { }16 };17 18 node* _LCA(node *root, int n1, int n2, bool &v1, bool &v2) {19 if (!root) return NULL;20 if (root->data == n1) {21 v1 = true;22 return root;23 }24 if (root->data == n2) {25 v2 = true;26 return root;27 }28 node *l = _LCA(root->left, n1, n2, v1, v2);29 node *r = _LCA(root->right, n1, n2, v1, v2);30 if (l && r) return root;31 return l? l : r;32 }33 34 bool findnode(node *root, int k) {35 if (!root) return false;36 return (root->data == k || findnode(root->left, k) || findnode(root->right, k));37 }38 39 node *LCA(node *root, int n1, int n2) {40 bool v1 = false;41 bool v2 = false;42 node *lca = _LCA(root, n1, n2, v1, v2);43 if (v1 && v2 || v1 && findnode(root, n2) || v2 && findnode(root, n1)) return lca;44 return NULL;45 }46 47 int main() {48 node *root = new node(1);49 root->left = new node(2);50 root->right = new node(3);51 root->left->left = new node(4);52 root->left->right = new node(5);53 root->right->left = new node(6);54 root->right->right = new node(7);55 cout << "LCA(4, 5) is " << LCA(root, 4, 5)->data << endl;56 cout << "LCA(4, 6) is " << LCA(root, 4, 6)->data << endl;57 cout << "LCA(3, 4) is " << LCA(root, 3, 4)->data << endl;58 cout << "LCA(2, 4) is " << LCA(root, 2, 4)->data << endl;59 return 0;60 }