视频直播网站建设方案,引流网站怎么做,肥城网站开发公司,长沙制作网站公司哪家好代码随想录刷题随记19-二叉树8
235. 二叉搜索树的最近公共祖先
leetcode 因为是有序树#xff0c;所以 如果 中间节点是 q 和 p 的公共祖先#xff0c;那么 中节点的数组 一定是在 [p, q]区间的。即 中节点 p 中节点 q 或者 中节点 q …代码随想录刷题随记19-二叉树8
235. 二叉搜索树的最近公共祖先
leetcode 因为是有序树所以 如果 中间节点是 q 和 p 的公共祖先那么 中节点的数组 一定是在 [p, q]区间的。即 中节点 p 中节点 q 或者 中节点 q 中节点 p 注意这里必须先访问根节点后序遍历不行 解题代码
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {TreeNode * cur;stackTreeNode* mystack;mystack.push(root);while(!mystack.empty()){curmystack.top();mystack.pop();if(curp||curq)return cur;if((cur-valp-valcur-valq-val)||(cur-valp-valcur-valq-val))return cur;if(cur-right!nullptr)mystack.push(cur-right);if(cur-left!nullptr)mystack.push(cur-left); } return nullptr;}
};701.二叉搜索树中的插入操作
leetcode链接 只要遍历二叉搜索树找到空节点 插入元素就可以了并不需要调整树的结构
class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {if(rootnullptr)return new TreeNode(val);TreeNode * curroot;TreeNode * prenullptr;while(cur!nullptr){precur;
… pre-rightnew TreeNode (val);return root;}
};450.删除二叉搜索树中的节点
leetcode链接
与插入不同删除节点涉及到修改树的结构 有点类似于两个搜索树要合并的意思 解题代码
在这里插入代码片有以下五种情况
第一种情况没找到删除的节点遍历到空节点直接返回了 找到删除的节点 第二种情况左右孩子都为空叶子节点直接删除节点 返回NULL为根节点 第三种情况删除节点的左孩子为空右孩子不为空删除节点右孩子补位返回右孩子为根节点 第四种情况删除节点的右孩子为空左孩子不为空删除节点左孩子补位返回左孩子为根节点 第五种情况左右孩子节点都不为空则将删除节点的左子树头结点左孩子放到删除节点的右子树的最左面节点的左孩子上返回删除节点右孩子为新的根节点。
class Solution {
public:TreeNode * subdel(TreeNode * cur){if(curnullptr)return nullptr;if(cur-leftnullptrcur-rightnullptr)return nullptr;if(cur-leftnullptr)return cur-right;if(cur-rightnullptr)return cur-left;TreeNode * tmpcur-right;while(tmp-left){tmptmp-left;}tmp-leftcur-left;tmpcur;curcur-right;tmp-rightnullptr;tmp-leftnullptr;delete tmp;return cur;}TreeNode* deleteNode(TreeNode* root, int key) {TreeNode * curroot;TreeNode * prenullptr;if(rootnullptr)return nullptr;while(cur!nullptr){ if(cur-valkey)break;precur;if(cur-valkey)curcur-right;else curcur-left;}//没找到if(curnullptr){return root;}//要删除的是根节点if(prenullptr)return subdel(root);if(pre-leftcur){pre-leftsubdel(cur);}else if(pre-rightcur){pre-rightsubdel(cur);}return root;}};
