fucking-algorithm 东哥带你刷二叉搜索树（基操篇）

评论礼仪见这里，违者直接拉黑。

Nov 20 '21 08:11 utterances-bot

注意一下，这个删除操作并不完美，因为我们一般不会通过 root.val = minNode.val 修改节点内部的值来交换节点，而是通过一系列略微复杂的链表操作交换 root 和 minNode 两个节点。因为具体应用中，val 域可能会是一个复杂的数据结构，修改起来非常麻烦；而链表操作无非改一改指针，而不会去碰内部数据。

这里我觉得其实问题的不大，如果是个复杂的数据结构，这里里修改root.val = minNode.val 也不过是修改一个地址而已，是吧

Nov 20 '21 08:11 biaoboss

@biaoboss 不是，如果不只有 val 字段呢？如果有的语言可能存的是值而不是指针呢？实际情况是你根本不知道 TreeNode 的里面的数据是什么样子，所以最好的办法就是不要动数据域，只单纯地操作数据结构，即只去操作 left 和 right 指针。

Nov 20 '21 13:11 labuladong

温馨提示：删除二叉树节点的思路过不了450.删除二叉搜索树中的节点（中等）这一题

Nov 24 '21 05:11 08163127cmut

@biaoboss 不是，如果不只有 val 字段呢？如果有的语言可能存的是值而不是指针呢？实际情况是你根本不知道 TreeNode 的结构，最好的办法就是不要动数据域，只单纯地操作数据结构。

关于指针操作替换 root 节点和 minNode 节点的代码，已经更新到文章中。

Nov 26 '21 14:11 labuladong

有个疑问："情况 3：A 有两个子节点，麻烦了，为了不破坏 BST 的性质，A 必须找到左子树中最大的那个节点，或者右子树中最小的那个节点来接替自己。" 按照性质，应该只能找到右子树最小节点来替代呀，为什么找左子树最大也成立呢

Dec 22 '21 21:12 mingxin1012

判断isValidBST, 也可以利用BST的inorder traversal 所有元素应该是递增的属性.

class Solution:
    def __init__(self):
        self.prev = float('-inf')
        self.bool = True
    
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        self.inorder(root)
        return self.bool
    
    def inorder(self, node):
        if node is None:
            return
        
        self.inorder(node.left)
        if self.prev == float('-inf'):
            self.prev = node.val
        else:
            if node.val <= self.prev:
                self.bool=False
            else:
                self.prev = node.val
        self.inorder(node.right)

Jan 03 '22 07:01 JackHo327

有个疑问："情况 3：A 有两个子节点，麻烦了，为了不破坏 BST 的性质，A 必须找到左子树中最大的那个节点，或者右子树中最小的那个节点来接替自己。" 按照性质，应该只能找到右子树最小节点来替代呀，为什么找左子树最大也成立呢

@ryanmingxinzhang 右子树最小和左子树最大不是对称的概念吗，既然右小可以接替原来的root，那左大必然可以，不存在谁更高贵

Jan 23 '22 09:01 ErronZrz

root.right = deleteNode(root.right, minNode.val); minNode.left = root.left; minNode.right = root.right;

为什么第一行和第二行交换一下顺序，答案就不对的啊，左子树应该不受影响啊

Jan 24 '22 07:01 zrguo

BST 代码框架，学到了学到了！！

Jan 30 '22 07:01 gcdd1993

deleteNoded存在内存泄漏吗?

Feb 03 '22 08:02 alexyuisme

js 98. 验证二叉搜索树

var isValidBST = function (root) {
  return check(root);

  /* 限定以 node 为根的子树节点必须满足 max > node.val > min */
  function check(node, min = -Infinity, max = Infinity) {
    // base case
    if (node === null) return true;
    // 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST
    if (node.val <= min || node.val >= max) {
      return false;
    }
    // 限定左子树的最大值是 node.val，右子树的最小值是 node.val
    return (
      check(node.left, min, node.val) &&
      check(node.right, node.val, max)
    );
  }
};

js 700. 二叉搜索树中的搜索

var searchBST = function(root, val) {
  if (root === null) return null;
  // 去左子树搜索
  if (val < root.val) return searchBST(root.left, val);
  // 去右子树搜索
  if (val > root.val) return searchBST(root.right, val);
  // 找到
  return root;
};

js 701. 二叉搜索树中的插入操作

var insertIntoBST = function (root, val) {
  // 找到空位置插入新节点
  if (root === null) return new TreeNode(val);
  // if (val === root.val)
  //     BST 中一般不会插入已存在元素
  if (val < root.val) {
    root.left = insertIntoBST(root.left, val);
  }
  if (val > root.val) {
    root.right = insertIntoBST(root.right, val);
  }
  return root;
};

js 450. 删除二叉搜索树中的节点

var deleteNode = function (root, key) {
  if (root === null) return null;

  if (root.val === key) {
    // 找到啦，进行删除
    // 恰好是末端节点，直接删除
    if (root.left === null && root.right === null) {
      return null;
    }

    // 只有一个非空子节点，那么它要让这个孩子接替自己的位置
    if (root.left !== null && root.right === null) return root.left;
    if (root.left === null && root.right !== null) return root.right;

    // 有两个非空子节点
    // 找到右子树的最小节点
    const rightMinNode = getMin(root.right);
    // 删除右子树最小的节点
    root.right = deleteNode(root.right, rightMinNode.val);
    // 把 root 改成 minNode
    rightMinNode.left = root.left;
    rightMinNode.right = root.right;
    root = rightMinNode;
  } else if (key < root.val) {
    // 去左子树找
    root.left = deleteNode(root.left, key);
  } else if (key > root.val) {
    // 去右子树找
    root.right = deleteNode(root.right, key);
  }

  return root;

  function getMin(node) {
    while (node.left) {
      node = node.left;
    }
    return node;
  }
};

Feb 09 '22 03:02 jswxwxf

一颗完整的 js 二叉搜索树实现：

class TreeNode {
  constructor(val) {
    this.val = val;
    this.count = 1;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(val, node = this.root) {
    // 处理空树
    if (this.root === null) {
      this.root = new TreeNode(val);
      return this.root;
    }
    // 找到空位置插入新节点
    if (node === null) return new TreeNode(val);
    // 找到，计数加 1
    if (val === node.val) node.count++;
    // 去左子树搜索
    if (val < node.val) node.left = this.insert(val, node.left);
    // 去右子树搜索
    if (val > node.val) node.right = this.insert(val, node.right);
    return node;
  }

  find(val, node = this.root) {
    if (node === null) return null;
    // 去左子树搜索
    if (val < node.val) return this.find(val, node.left);
    // 去右子树搜索
    if (val > node.val) return this.find(val, node.right);
    // 找到
    return node;
  }

  remove(val, node = this.root) {
    // 没找到
    if (node === null) return null;

    if (node.val === val) {
      // 找到啦，进行删除
      // 恰好是末端节点，直接删除
      if (node.left === null && node.right === null) {
        return null;
      }

      // 只有一个非空子节点，那么它要让这个孩子接替自己的位置
      if (node.left !== null && node.right === null) return node.left;
      if (node.left === null && node.right !== null) return node.right;

      // 有两个非空子节点
      // 找到右子树的最小节点
      const rightMinNode = this.getMinNode(node.right);
      // 删除右子树最小的节点
      node.right = this.remove(rightMinNode.val, node.right);
      // 把 root 改成 minNode
      rightMinNode.left = node.left;
      rightMinNode.right = node.right;
      node = rightMinNode;
    } else if (val < node.val) {
      // 去左子树找
      node.left = this.remove(val, node.left);
    } else if (val > node.val) {
      // 去右子树找
      node.right = this.remove(val, node.right);
    }

    return node;
  }

  getMinNode(node = this.root) {
    while (node.left) {
      node = node.left;
    }
    return node;
  }

  getMaxNode(node = this.root) {
    while (node.right) {
      node = node.right;
    }
    return node;
  }

  bfs() {
    if (this.root === null) return [];
    const list = [];
    const q = [this.root];
    while (q.length) {
      const sz = q.length;
      for (let i = 0; i < sz; i++) {
        const node = q.shift();
        list.push(node.val);
        if (node.left) q.push(node.left);
        if (node.right) q.push(node.right);
      }
    }
    return list;
  }

  dfsPreOrder(node = this.root, list = []) {
    if (this.root === null) return [];
    list.push(node.val);
    if (node.left) this.dfsPreOrder(node.left, list);
    if (node.right) this.dfsPreOrder(node.right, list);
    return list;
  }

  dfsInOrder(node = this.root, list = []) {
    if (this.root === null) return [];
    if (node.left) this.dfsInOrder(node.left, list);
    list.push(node.val);
    if (node.right) this.dfsInOrder(node.right, list);
    return list;
  }

  dfsPostOrder(node = this.root, list = []) {
    if (this.root === null) return [];
    if (node.left) this.dfsPostOrder(node.left, list);
    if (node.right) this.dfsPostOrder(node.right, list);
    list.push(node.val);
    return list;
  }
}

const tree = new BinarySearchTree();
tree.insert(9);
tree.insert(9);
tree.insert(4);
tree.insert(6);
tree.insert(20);
tree.insert(170);
tree.insert(15);
tree.insert(1);

console.log(tree.bfs());
console.log(tree.dfsPreOrder());
console.log(tree.dfsInOrder());
console.log(tree.dfsPostOrder());

console.log(tree.find(15));
console.log(tree.remove(15));
console.log(tree.find(15));

Feb 09 '22 03:02 jswxwxf

@Zoran-Kwok minNode是右子树的一个节点，第二行和第一行交换位置，意味着你修改了右子树，再去执行deleteNode

Feb 28 '22 10:02 renlindong

@labuladong,判断BST的合法性的正确代码那个，判断方法是改变了吗？就是从判断当前节点大于左孩子，小于右孩子，改为了当前节点的左子树都小于当前节点，当前节点的右子树都大于当前节点吗？？有点不理解这个min，和max，总感觉判断左子树时isValidBST(root.left, min, root) ，这个min会一直传递null。判断右子树时isValidBST(root.right, root, max);的max会一直传递null。再以当前节点大于左孩子，小于右孩子来判断，无法理解这个代码。。。 boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) { // base case if (root == null) return true; // 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST if (min != null && root.val <= min.val) return false; if (max != null && root.val >= max.val) return false; // 限定左子树的最大值是 root.val，右子树的最小值是 root.val return isValidBST(root.left, min, root) && isValidBST(root.right, root, max); }

Mar 04 '22 04:03 Jackwong0716

@Jackwong0716

//关注当前节点与左右孩子的行为
//当前结点root的左孩子root.left
max = root.val；
min = min;//最小值保持不变
//当前结点root的右孩子root.right
min = root.val，
max = max;//最大值保持不变
//左右孩子分别将root的min， max约束传递下来

//min只有从根一直向左传递才会为null
//max只有从根一直向右传递才会为null
//中途只要变过方向约束条件都会变

Mar 07 '22 03:03 mingy-z

我发现不对劲的地方，450 题，删除二叉搜索树的节点里面作者所说的「如果要删除的点的左右孩子都不为 null，那么需要找左子树中最大或右子树中最小的点来接替自己」是没必要的需要做的只是，让左孩子接替自己，右孩子去自己能去到的最右的地方即可比如说 {4,2,6,1,3,5,7}（层次遍历顺序）这棵子树需要删掉 4，不一定要 3 或者 5 来代替自己的位置，而是只需要用它的左孩子 2 来代替自己，变成 {2,1,3,null,null,null,6,5,7}，同样是合法的 BST 这样就可以简化很多步骤

Mar 10 '22 00:03 ErronZrz

@ErronZrz 多思考是好的，但需要用实践来检验想法，不妨把你实现的代码贴出来

Mar 11 '22 12:03 labuladong

@ErronZrz 多思考是好的，但需要用实践来检验想法，不妨把你实现的代码贴出来

@labuladong 代码如下：

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(null==root){
            return null;
        }
        if(key < root.val){
            root.left = deleteNode(root.left, key);
        }else if(key > root.val){
            root.right = deleteNode(root.right, key);
        }else{
            if(null==root.left){
                return root.right;
            }
            if(null==root.right){
                return root.left;
            }
            TreeNode cur = root.left;
            while(null != cur.right){
                cur = cur.right;
            }
            cur.right = root.right;
            return root.left;
        }
        return root;
    }
}

Mar 11 '22 13:03 ErronZrz

@ErronZrz 理解了，你是把左子树替换到根节点，然后把原来的右子树放到原来的左子树中正确的位置，这样的确也能正确维护 BST 的性质

Mar 11 '22 14:03 labuladong

// 处理情况 3
// 获得右子树最小的节点
TreeNode minNode = getMin(root.right);
// 删除右子树最小的节点
root.right = deleteNode(root.right, minNode.val);
// 用右子树最小的节点替换 root 节点
root.val = minNode.val;

删除右子树最小节点是否可以和查找结合起来，最小节点一定是最左的叶子节点，getMin 返回其父节点，删除操作仅需将 partMinNode.left = null 就行了吧

Apr 08 '22 08:04 zhyozhi

想请问一个问题，为什么在二叉搜索树的第一种情况下

if (root.left == null && root.right == null)
    return null;

为什么不是root=null,而是直接返回null

Apr 10 '22 01:04 cillian-bao

@cillian-bao 上层递归接收空指针，才能从结构中删掉对应节点。

Apr 11 '22 03:04 labuladong

nice

Apr 22 '22 04:04 cheng-miao

Hibbard deletion，挺经典的，我记得算法四里面还多一步，删除的时候还要计算node size👍

Apr 22 '22 20:04 Sm1te

提问，插入节点到BST那题，怎么证明任何值都能插在叶节点后面？

May 21 '22 09:05 itsangona

删除BST结点的第三种情况：情况 3：A 有两个子节点，麻烦了，为了不破坏 BST 的性质，A 必须找到左子树中最大的那个节点，或者右子树中最小的那个节点来接替自己。这是否也不唯一？也可以将被删除结点的左子树整个接到右子树的最左的叶子节点上即可。

May 25 '22 08:05 Maxiah

@Maxiah 方法确实有很多种，但你说的这个方案不好，因为你这样会显著提高 BST 的高度，实际应用会大幅降低 BST 的搜索效率。

May 30 '22 13:05 labuladong

很经典,就是没那么直观,要想一会才能看懂,比如第一题我是这么理解的:min的值是当前root的取值下限,max的值其实就是当前root的取值上限,超出这个范围就达到了递归出口,传参null,意思其实就是(-∞,+∞)

Jun 01 '22 08:06 LebronHarden1

请问博主有没有BST插入多个数讲解,从而维护BST的性质？

Jun 01 '22 08:06 huangbenliang

Golang实现的

func deleteNode(root *TreeNode, key int) *TreeNode {
	if root == nil {
		return nil
	}
	if key < root.Val {
		root.Left = deleteNode(root.Left, key)
		return root
	} else if key > root.Val {
		root.Right = deleteNode(root.Right, key)
		return root
	}
	//与本节点相同的情况
	if root.Left == nil && root.Right == nil {
		return nil
	} else if root.Left == nil && root.Right != nil {
		return root.Right
	} else if root.Left != nil && root.Right == nil {
		return root.Left
	}
	root.Val, root.Right = FoundMin(root.Right)
	return root
}
func FoundMin(root *TreeNode) (int, *TreeNode) { //返回树的最小值，并删除最小值节点
	if root.Left == nil {
		return root.Val, root.Right
	}
	var temp int
	temp, root.Left = FoundMin(root.Left)
	return temp, root
}

Jul 13 '22 08:07 ueueQ

fucking-algorithm
fucking-algorithm copied to clipboard

东哥带你刷二叉搜索树（基操篇） :: labuladong的算法小抄

fucking-algorithm fucking-algorithm copied to clipboard

东哥带你刷二叉搜索树（基操篇） :: labuladong的算法小抄

fucking-algorithm
fucking-algorithm copied to clipboard