Leetcode 235 Lowest Common Ancestor of a Binary Search Tree 二叉树

给定一个二叉搜索树的两个节点，找出他们的最近公共祖先，如，

        _______6______

       /              \

    ___2__          ___8__

   /      \        /      \

  0        4       7       9

          /  \

         3    5

2和8的最近公共祖先是6，2和4的最近公共祖先是2，假设找的3和5

TreeNode* l =lowestCommonAncestor(root->left,p,q) ;
TreeNode* r =lowestCommonAncestor(root->right,p,q) ;

返回到4时两个都不是Nullptr，那么要返回4的指针即if(l && r ) return root;
返回到2时只有r是Nullptr，那么要返回4的指针即else if(!l && r) return r;
返回到6时只有l是Nullptr，那么要返回4的指针即else if(l && !r) return l;
返回到8时都是是Nullptr，那么返回NULL 即else return NULL;

本文的求解方法没有利用二叉搜索树的特点，因此效率较低

 /**

  * Definition for a binary tree node.

  * struct TreeNode {

  *     int val;

  *     TreeNode *left;

  *     TreeNode *right;

  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

  * };

  */

 class Solution {

 public:

     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

         if(!root) return NULL;

         else if(!q&&!p){

             return NULL;

         }

         else if(root->val == p->val){

             return root;

         }

         else if(q->val == root->val){

             return root;

         }

         else {

             TreeNode* l =lowestCommonAncestor(root->left,p,q) ;

             TreeNode* r =lowestCommonAncestor(root->right,p,q) ;

             if(l && r ) return root;

             else if(!l && r) return r;

             else if(l && !r) return l;

             else return NULL;

         }

     }

 };

巴特西

Leetcode 235 Lowest Common Ancestor of a Binary Search Tree 二叉树

最新文章

热门文章