做网站都需要考虑哪些,ui私活20个页面以上多少钱,WordPress地址不能修改,wordpress 搬家 后台二叉树为BST LCR 193. 二叉搜索树的最近公共祖先
1.1 递归
利用BST的性质
p root 或者 q root ,显然根为公共祖先p root q 或者 p root q,显然p#xff0c;q分别位于root的一颗子树上#xff0c;故根为公共祖先max{p,q} root ,显然 p 和q 均在… 二叉树为BST LCR 193. 二叉搜索树的最近公共祖先
1.1 递归
利用BST的性质
p root 或者 q root ,显然根为公共祖先p root q 或者 p root q,显然pq分别位于root的一颗子树上故根为公共祖先max{p,q} root ,显然 p 和q 均在root的左子树min{p,q} root ,显然 p 和q 均在root的右子树
/*** 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;if(root-val p-val || root-val q-val)return root;if(root-val q-val root-val p-val)return root;if(root-val q-val root-val p-val)return root;if(root-val p-val root-val q-val)return lowestCommonAncestor(root-right,p,q);if(root-val p-val root-val q-val)return lowestCommonAncestor(root-left,p,q);return root;}
};1.2 迭代
利用后序遍历递归的特点当访问结点p时此时栈中存储结点 时 自顶向下的祖先
利用后序遍历获取p和q的祖先序列因最近公共祖先 所在层数 一定 ≤ min{ stack_p.size() , stack_q.size() }故先通过出栈让p和q中祖先数量相等即二者祖先 处于同一层上当 出栈 到 二者祖先相同时便为最近公共祖先
/*** 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:stackTreeNode* searchAncestor(TreeNode* root,TreeNode* p){stackTreeNode* s;TreeNode* pre;while(root || s.size()){if(root){s.push(root);root root-left;}else{TreeNode* node s.top();if(node-val p-val) break;if(node-right pre ! node-right){root node-right;}else{s.pop();pre node;cout node-val ;root NULL;}}}return s;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(!root)return NULL;stackTreeNode* stack_p searchAncestor(root,p);stackTreeNode* stack_q searchAncestor(root,q);while(stack_p.size() stack_q.size()) stack_p.pop();while(stack_q.size() stack_p.size()) stack_q.pop();while(stack_p.size() stack_q.size()){if(stack_p.top() stack_q.top())return stack_p.top();else{stack_p.pop();stack_q.pop();}}return root;}
};任意二叉树 LCR 194. 二叉树的最近公共祖先
/*** 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:stackTreeNode* searchAncestor(TreeNode* root,TreeNode* p){stackTreeNode* s;TreeNode* pre;while(root || s.size()){if(root){s.push(root);root root-left;}else{TreeNode* node s.top();if(node-val p-val) break;if(node-right pre ! node-right){root node-right;}else{s.pop();pre node;cout node-val ;root NULL;}}}return s;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(!root)return NULL;stackTreeNode* stack_p searchAncestor(root,p);stackTreeNode* stack_q searchAncestor(root,q);while(stack_p.size() stack_q.size()) stack_p.pop();while(stack_q.size() stack_p.size()) stack_q.pop();while(stack_p.size() stack_q.size()){if(stack_p.top() stack_q.top())return stack_p.top();else{stack_p.pop();stack_q.pop();}}return root;}
};
