235. 二叉搜寻树的最近公共先人
题意：
(1)所有节点的值都是惟一的。
(2)p、q 为不同节点且均存在于给定的二叉搜寻树中。
剖析
分3种状况：
(1) p、q别离在root左右子树中。此时root即为最近公共先人
(2) p、q都在左子树中，最近公共先人在左子树中，遍历左子树
(3) p、q都在右子树中，遍历右子树
题解
1、递归
class Solution {public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if((root->val - p->val) * (root->val - q->val) <= 0) return root; if(root->val > p->val) return lowestCommonAncestor(root->left, p, q); else return lowestCommonAncestor(root->right, p, q); }};2、迭代
class Solution {public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { while(1) { if((root->val - p->val) * (root->val - q->val) <= 0) return root; if(root->val > p->val) root = root->left; else root = root->right; } return root; }};236. 二叉树的最近公共先人
办法一：递归
后序遍历，当遇到节点p或q时返回，故依据返回值得出pq是否在子树中。
因为是后序遍历，故第一次碰到节点p,q在节点root的异侧时[包含root==p或q的状况]，节点root即为最近公共先人，则向上返回root。
class Solution {public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root == nullptr || root == p || root == q) return root; TreeNode* l = lowestCommonAncestor(root->left, p, q); TreeNode* r = lowestCommonAncestor(root->right, p, q); if(!l && !r) return nullptr; //(1) if(!l) return r; //(3) if(!r) return l; //(4) return root; //(2) if(left != NULL and right != NULL) }};返回值：依据left和right，可开展为四种状况；
- 当left和 right 同时为空：阐明root的左/右子树中都不蕴含 p,q，返回null；
- 当left和 right 同时不为空：阐明p,q分列在root的 异侧（别离在左/右子树），因而root为最近公共先人，返回 root；
- 当left为空 ，right不为空：p,q都不在root的左子树中，间接返回 right。具体可分为两种状况：
p,q其中一个在root的右子树中，此时right指向p（假如为p）；
p,q两节点都在root的右子树中，此时的right指向最近公共先人节点 ； - 当 left不为空，right为空：与状况 3. 同理;
- 工夫复杂度O(N)：其中N为二叉树节点数；最差状况下，须要递归遍历树的所有节点。
- 空间复杂度O(N)：最差状况下，递归深度达到N，零碎应用O(N)大小的额定空间。
参考
链接：https://leetcode.cn/problems/...