TreeNode findLCA(TreeNode root, TreeNode p, TreeNode q) { // no root no LCA. if(!root) { return NULL; } // if either p or q is the root then root is LCA. if(root==p || root==q) { return root; } else { // get LCA of p and q in left subtree. TreeNode l=findLCA(root->left , p , q); // get LCA of p and q in right subtree. TreeNode r=findLCA(root->right , p, q); // if one of p or q is in leftsubtree and other is in right // then root it the LCA. if(l && r) { return root; } // else if l is not null, l is LCA. else if(l) { return l; } else { return r; } } }
这个面试太常出现了,所以更新下。最主要用buttom up效率高,O(n), 思路其实类似isBalanced Binary Tree.