LeetCode刷题day42

//递归法   主要是寻找区间 [p,q],root在这个区间之间,那么root就是公共祖先. 
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  if(root==NULL){
    return NULL;
  }
  //左子树
  if(root->val > p->val && root->val > q->val){//注意p,和q的大小是未知的,所以两个都要进行比较 
    TreeNode* left = lowestCommonAncestor(root->left,p,q);//遍历一条边的做法 
    if(left){//如果最后不为空则说明找到了,则直接进行返回 
      return left;
    } 
  } 
  if(root->val < p->val && root->val < q->val){
    TreeNode* right = lowestCommonAncestor(root->right,p,q);
    if(right){
      return right;
    }
  } 
  return root;//如果root->val 即不都大于p,q;又不都小于p,q; 则说明root肯定是位于p,q之间的 
}

//递归法
void traversal(TreeNode* root,int val) {
  if(val < root->val) { //递归法的野路子.. 
    if(!root->left) {//直接在本层判断左子树是否为空 
      root->left = new TreeNode(val);
    } else {
      traversal(root->left,val);
    }
  }
  if(val > root->val) {
    if(!root->right) {//在递归之前判断右子树是否为空.. 
      root->right = new TreeNode(val);
    } else {
      traversal(root->right,val);
    }
  }
  return;
}
TreeNode* insertIntoBST(TreeNode* root, int val) {
  if(root==NULL) {
    root = new TreeNode(val);
  }
  traversal(root,val);
  return root;
}

TreeNode* parent = new TreeNode(0);
void traversal(TreeNode* cur,int val) {
  if(cur == NULL){
    TreeNode* node = new TreeNode(val);
    if(val > parent->val){
      parent->right = node;
    }else{
      parent->left  = node;
    }
    return;
  }
  parent = cur;
  if(val < cur->val){
    traversal(cur->left,val);
  }else if(val > cur->val){
    traversal(cur->right,val);
  }
  return;
}
TreeNode* insertIntoBST(TreeNode* root, int val) {
  if(root==NULL){
    root = new TreeNode(0);
  } 
  traversal(root,val);
  return root;
}

TreeNode* insertIntoBST(TreeNode* root, int val) {
  if(root==NULL){//如果节点为空了,则直接以val创建节点并返回 
    return new TreeNode(val);
  } 
  if(val < root->val){//向左子树寻找插入的位置. 
    root->left = insertIntoBST(root->left,val);
  }
  if(val > root->val){//向右边子树寻找插入的位置
    root->right = insertIntoBST(root->right,val);
  }
  return root;
}

//迭代法 
TreeNode* insertIntoBST(TreeNode* root, int val) {
  if(root==NULL){
    root = new TreeNode(val);
    return root;
  }
  TreeNode* pre=NULL;//插入节点一般就定义两个变量,不要在想着用野套路本次判断下一次然后插入节点...太混乱了. 
  TreeNode* cur = root;
  while(cur!=NULL){
    pre = cur;//更新上一个节点  必须在这里进行更新,因为下面cur就发生变化了 
    if(val < cur->val){//这里不可以分开成两个if哦!因为一旦分开,第二个if中的cur就和第一个if中的cur不同了,很可能出错. 
      cur = cur->left;
    }else if(val > cur->val){
      cur = cur->right;
    } 
  }
  //在pre上插入val节点
  if(val < pre->val){
    pre->left = new TreeNode(val);
  }else if(val > pre->val){
    pre->right = new TreeNode(val);
  } 
  return root;
} 

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]

TreeNode* deleteNode(TreeNode* root, int key) {
  // 第一种情况:没找到删除的节点 ,遍历到空节点直接返回NULL
  if(root==NULL) {
    return root;
  }
  //第二种情况:找到了删除的节点,对于删除操作要分成四种情况,并且每次都要返回当前子树 的根节点给上一层.(因为删除节点后指向会变更)
  if(root->val == key) {
    if(!root->left && !root->right) { //1.当左右孩子都为空,直接删除节点,返回NULL
      delete root;
      return NULL;
    } else if(!root->right) {//2.当左孩子不为空,右孩子为空,删除节点左孩子补位.返回左孩子
      TreeNode* temp = root->left;
      delete root;
      return temp;
    } else if(!root->left) { //3.当右孩子不为空,左孩子为空,删除节点右孩子补位.返回右孩子
      TreeNode* temp = root->right;
      delete root;
      return temp;
    } else {//4.当左右孩子都不为空,则将删除节点的左子树 移到删除节点右子树的最左孩子位置上;并返回删除节点的右子树
      TreeNode *cur = root->right;
      while(cur->left) { //寻找删除节点的最左侧节点
        cur = cur->left;
      }
      cur->left = root->left;//移到删除节点右子树的最左孩子位置上
      TreeNode* temp = root->right;
      delete root;
      return temp;
    }
  }
  //第三种情况:暂时还没有找到要删除的节点
  if(key < root->val) {
    root->left = deleteNode(root->left,key);
  } else if(key > root->val) {
    root->right = deleteNode(root->right,key);
  }
  return root;
}