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

[utterances-bot]

文章链接点这里：东哥带你刷二叉搜索树（基操篇）

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

[biaoboss]

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

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

[labuladong]

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

[labuladong]

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

[08163127cmut]

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

[llxblhyvia]

？可以啊

[mingxin1012]

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

[JackHo327]

判断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)

[codezs09]

+1
c++ 版本

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        res = true; 
        traverse(root); 
        return res;
    }

    void traverse(TreeNode* root) {
        if (root == nullptr)
            return;
        traverse(root->left); 
        if (is_last_val_set == false) {
            is_last_val_set = true; 
        } else if (root->val <= last_val) {
            res = false; 
        }
        last_val = root->val; 
        traverse(root->right);
    }

    int last_val;   // in inorder sequence
    bool is_last_val_set = false; 
    bool res; 
};

[ErronZrz]

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

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

[zrguo]

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

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

[HJinPeng]

minNode.left的左子树确实不受影响。但是右子树受影响了。原因如下：
如果先minNode.left = root.left; 那么右子树的最小节点的left也加上了root.left（因为是同一个引用地址），右子树已变化，此时你再执行root.right = deleteNode(root.right, minNode.val); 结果就不对啦。

[gcdd1993]

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

[alexyuisme]

deleteNode�d存在内存泄漏吗?

[sucongCJS]

C++的话，存在吧

[forexgg]

不会有内存泄漏。
Python 有垃圾回收机制。
Python的垃圾收集主要使用的是引用计数机制，每当一个对象被一个变量引用时，它的引用计数就会增加1；当引用它的变量被删除，或者变量被赋予新的对象时，它的引用计数就会减少1。当引用计数变为0时，对象就会被删除。

[jswxwxf]

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;
  }
};

[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));

[renlindong]

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

[mingy-z]

@Jackwong0716

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

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

[ErronZrz]

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

[labuladong]

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

[labuladong]

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

[LebronHarden1]

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

[huangbenliang]

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

[ueueQ]

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
}

[deepbreath373]

----------check in

[loftiest]

java : 450 删除二叉树结点 可通过
找到节点，然后遍历该节点的右子树的左子树，将该节点的左子树接到其右子树的左子树，返回右子树；最后，将右子树连接到该节点的上一个节点上。

public TreeNode deleteNode(TreeNode root, int key) {
        if ( root == null ) { return null; }
        if ( root.val == key ) {
            return insertNode(root.right,root.left);
        }
        else if ( root.val > key ) {
            root.left = deleteNode(root.left,key);
        }
        else {
            root.right = deleteNode(root.right,key);
        }
        return root;
    }
    TreeNode insertNode(TreeNode root, TreeNode tree){
        if ( root == null ) { return tree; }
        root.left = insertNode(root.left,tree);
        return root;
    }

[yonggui-yan]

打卡

[jxs1211]

go version for delete node

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil {return nil}
    if root.Val == key {
        if root.Left == nil {return root.Right}
        if root.Right == nil {return root.Left}
        if root.Left == nil && root.Right == nil {
            return nil
        }
        if root.Left != nil && root.Right != nil {
            // 1 record minNode
            minNode := getMinNode(root.Right)
            // 2 delete minNode and update root.Right
            root.Right = deleteNode(root.Right, minNode.Val)
            // 3 replace root with minNode
            minNode.Left, minNode.Right = root.Left, root.Right
            // root.Val = r.Val
            root = minNode
        }
    }
    if key < root.Val {
        root.Left = deleteNode(root.Left, key)
    }
    if key > root.Val {
        root.Right = deleteNode(root.Right, key)
    }
    
    return root
}

func getMinNode(root *TreeNode) *TreeNode {
    if root == nil {return nil}
    if root.Left == nil {return root}
    return getMinNode(root.Left)
}

func getMinNode2(root *TreeNode) *TreeNode {
    if root == nil {return nil}
    for root.Left != nil {
        root = root.Left
    }
    return root
}

[daixiongming]

东哥你的总结太完美了，比huifeng guan的要好！

[Moyu0v0]

验证二叉搜索树可以利用BST的中序遍历特性：

class Solution {
    // 记录中序遍历的前驱
    TreeNode pre;
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        // 判断左子树
        if (!isValidBST(root.left)) {
            return false;
        }
        // 判断中序遍历的结果是否合法
        if (pre != null && pre.val >= root.val) return false;
        // 更新中序遍历的前驱
        pre = root;
        // 判断右子树
        return isValidBST(root.right);
    }
}

[EyeDroplyq]

提个疑问，希望有人解答一下： 在进行操作root = minNode; 的时候，为啥不用将root的做右指针断开

[EyeDroplyq]

试过了，置空也可以的，个人感觉还是置空更严谨

[zhangmuwuge]

java垃圾自动回收

[llxblhyvia]

python3实现，把return的地方改的更统一且傻瓜了一些hhhh

class Solution(object):
    def deleteNode(self, root, key):
        if not root:
            return root

        if root.val == key:
            if root.right is None:
                root = root.left
                return root
            if root.left is None:
                root = root.right
                return root

            minNode = self.getMin(root.right)
            root.right = self.deleteNode(root.right, minNode.val)
            minNode.right = root.right
            minNode.left = root.left
            root = minNode
            return root

        elif root.val < key:
            root.right = self.deleteNode(root.right, key)
        elif root.val > key:
            root.left = self.deleteNode(root.left, key)
        return root

    def getMin(self, root):
        while root.left:
            root = root.left
        return root

[fangyuan99]

看到一种关于力扣第 98 题「验证二叉搜索树」就是让你判断输入的 BST 是否合法的解法，通过中序遍历解决。

class Solution {
    long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 访问左子树
        if (!isValidBST(root.left)) {
            return false;
        }
        // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        // 访问右子树
        return isValidBST(root.right);
    }
}

作者：Sweetiee 🍬
链接：https://leetcode.cn/problems/validate-binary-search-tree/solutions/232885/zhong-xu-bian-li-qing-song-na-xia-bi-xu-miao-dong-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

[fangyuan99]

和sum那个题异曲同工，注意这里要用long类型

[GuohyCoding]

有一点不是很明白，在递归的时候，如果只是查询则直接return BST(root.left, target);，如果涉及改则需要接收返回值root.left = BST(root.left, target);，请问这是为什么呢？

[hualuo321]

450. 删除二叉搜索树中的节点 【BST】【遍历】【中序】【C++】

class Solution {
private:
    int key;
    int bak;    // 删除交换后的节点后, 用于恢复原始的 key
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        this->key = key;
        this->bak = key;
        return traverse(root);
    }

    // 先通过遍历找到需要删除的节点
    // 然后将其删除
    TreeNode* traverse(TreeNode* root) {
        if (root == nullptr) return nullptr;
        if (root->val == key) {
            if (root->left == nullptr && root->right == nullptr) {
                return nullptr;
            } else if (root->left == nullptr){
                return root->right;
            } else if (root->right == nullptr) {
                return root->left;
            } else {
                TreeNode* mini = getMin(root->right);
                key = mini->val;
                root->right = traverse(root->right);
                key = bak;
                mini->left = root->left;
                mini->right = root->right;
                root = mini;
            }
        } else if (root->val > key) {
            root->left = traverse(root->left);
        } else {
            root->right = traverse(root->right);
        }
        return root;
    }

    // 获取以该节点开始的最小节点
    TreeNode* getMin(TreeNode* root) {
        while (root->left != nullptr) {
            root = root->left;
        }
        return root;
    }
};

[fear666]

700.二叉搜索树中的搜索

我的思考

如果使用递归遍历二叉树的思路，其实递归总是会返回给上层的。

这题我的思路，分为两种情况
i. 走到叶子节点下面的nil了，都没搜到，说明没有符合的节点
ii. 命中相应的值

代码

使用GO语言解答

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func searchBST(root *TreeNode, val int) *TreeNode {
    node := root
    for node != nil && node.Val != val { //跳出循环的条件，节点为空>整棵树都没有符合条件的 或者 节点的值等于搜索的值>这个节点就是答案
        if node.Val > val {
            node = node.Left
        } else { //node.Val < val
            node = node.Right
        }
    }
    return node
}