最专业的企业营销型网站建设价格,网络营销推广公司简介,美工做兼职在那个网站,网络推广员压力大吗目录
700 二叉搜索树中的搜索
迭代
递归
450 删除二叉搜索树中的节点 700 二叉搜索树中的搜索 注意二叉搜索树的性质即可 迭代
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {while(root ! NULL){if(root-val val)root root-r…目录
700 二叉搜索树中的搜索
迭代
递归
450 删除二叉搜索树中的节点 700 二叉搜索树中的搜索 注意二叉搜索树的性质即可 迭代
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {while(root ! NULL){if(root-val val)root root-right;else if(root-val val)root root-left;else return root;}return NULL;}
};
时间复杂度O(n)
空间复杂度O(n)
递归
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if(root NULL)return NULL;if(root-val val)return root;return root-val val?searchBST(root-left,val) : searchBST(root-right,val); }
};
时间复杂度O(n)
空间复杂度O(1)
450 删除二叉搜索树中的节点 在删除待删除节点时有如下五种情况 没找到待删除节点遍历到空节点后返回待删除节点左右节点都为空删除后直接返回空待删除节点左节点为空右节点不为空删除节点后让右孩子作为根节点待删除节点右节点为空左节点不为空删除节点后让左孩子作为根节点待删除节点左右节点都不为空将待删除节点的左孩子放到右孩子的最左节点的左孩子处返回待删除节点的右孩子作为根节点 class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if(root NULL)return NULL;//情况一if(root-val key){if(root-left NULL root-right NULL)return NULL;//情况二else if(root-left NULL root-right ! NULL)return root-right;//情况三else if(root-left ! NULL root-right NULL)return root-left;//情况四else{//情况五TreeNode* cur root-right;while(cur-left ! NULL){cur cur-left;}cur-left root-left;return root-right;}}if(root-val key)root-left deleteNode(root-left,key);if(root-val key)root-right deleteNode(root-right,key);return root;}
};
时间复杂度O(n)
空间复杂度O(n)
