木易

# Road Map

打怪路线：

  • 构建二叉搜索树：108 -> 1008 -> 449
  • 验证二叉搜索树：96 -> 95 -> 98
  • 二叉搜索树中的节点操作：700 -> 701 -> 450 -> 669
  • 搜索树中的迭代器：173 -> 230

# 二叉搜索树

# 二叉搜索树的性质

  • 结点左子树中所含结点的值小于等于当前结点的值
  • 结点右子树中所含结点的值大于等于当前结点的值
  • 左子树和右子树都是二叉搜索树

# 判断条件

  • 中序遍历是递增序列的二叉树一定是二叉搜索树，可以利用中序遍历是否有序判断是否二叉搜索树
  • 根节点大于所有左子树节点，如果根节点大于左子树的最大值节点即可，因为左子树的最大值位于左子树最右边的节点，所以只要根节点 > 左子树的最右节点即可；同理，根节点 < 右子树的最左节点；

# 寻找后继节点

public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    if (root == null) return null;
    if (root.val <= p.val) return inorderSuccessor(root.right, p);
    TreeNode ans = inorderSuccessor(root.left, p);
    return ans == null ? root : ans;
}
1
2
3
4
5
6
  • 分两种情况，当前节点 跟 p 节点大小比较
    • 当前节点 <= p 时，后继节点在右边
    • 当前节点 > p 时，后继节点是 当前节点最左边的节点

# 寻找左子树的最右节点（寻找右子树的最左节点）

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

# 98.验证二叉搜索树

# 530.二叉搜索树的最小绝对差

# 501.二叉搜索树中的众数

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

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

# 669. 修剪二叉搜索树

# 108.将有序数组转换为二叉搜索树

# 538.把二叉搜索树转换为累加树

# 题目

# 二叉树练习

← 0x47_树状数组 →