第一章：手把手带你刷二叉搜索树-第一期
labuladong
LeetCode
发布日期:   2021-09-27
作者:   M
文章字数:   2.1k
阅读时长:   9 分
热度:  

labuladong手把手带你刷二叉搜索树-第一期

  • 二叉树
    • 二叉树算法设计的总路线：把当前节点要做的事做好，其他的交给递归框架，不用当前节点操心。 （可以理解成递归方法的应用）
      • 明确递归结束的条件 （已经到了叶子节点）
      • 把root该做的事情做完， 然后左右子节点递归调用该方法
    • 如果当前节点会对下面的子节点有整体影响，可以通过辅助函数增长参数列表，借助参数传递信息。
void traverse(TreeNode root) {
    // root 需要做什么？在这做。
    // 其他的不用 root 操心，抛给框架
    traverse(root.left);
    traverse(root.right);
}

比如这道例题：

100. 相同的树

  • 函数内先判断两个root节点是否相等，然后递归调用该函数，判断左右子节点是否相等
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if p==None and q ==None: return True # 都为空节点
        if p==None or q ==None: return False # 其中一个为空节点（上一行已经判断了都空的情况）
        if p.val!=q.val:return False # 值不相等
        # 调用递归，判断左右子树是否都满足isSameTree
        return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
  • 二叉搜索树
    • 定义：任意节点的值要大于等于左子树所有节点的值，且要小于等于右子树的所有节点的值。
    • 因此，中序遍历二叉搜索树后，可以得到递增数组。
void BST(TreeNode root, int target) {
    if (root.val == target)
        // 找到目标，做点什么
    if (root.val < target) 
        BST(root.right, target);
    if (root.val > target)
        BST(root.left, target);
}

230. 二叉搜索树中第K小的元素

写法1：构造辅助递归函数

构造一个辅助的递归函数traverse()

  • 递归函数的含义（不要跳进递归中）：采用中序遍历的方式，更新当前的root节点对应的排序（因为这是二叉搜索树，也就是统计此时的节点数量）
    • e.g.,执行traverse(root->left, k); 后，rank变为2。然后当前节点需要做的事情：用rank++增加，则当前节点的排序变为3.如果排序与k相同，则结果就是此时的root值，用return结束递归。否则执行中序遍历的“后”。

需要两个变量：

  • 用一个全局变量保存最终的结果；
  • 用一个全局变量保存当前访问到第几个节点。

如果不使用全局变量，而是使用函数传参，需要注意「值传递」和「引用传递」的区别：值传递：每个递归的内部都需要对同一个变量修改，如果用普通函数的传参，对于 int 型的参数，使用的是值传递，即拷贝了一份传到了函数里面。那么函数里面对 int 型的修改不会影响外边的变量。

使用全局变量，可以保证递归函数的每次修改都是反映到全局的，从而保证遍历到第 k 个的时候，所有的递归立刻停止。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int res=0;//    保存结果
    int rank=0;// 保存当前root对应的排名
    void traverse(TreeNode* root, int k){
        if (root== nullptr) return; // 递归结束的条件
        traverse(root->left, k); // 中序遍历：前
//        中序遍历：中
        rank++;
        if (rank == k){
            res=root->val;
            return;
        }
        traverse(root->right,k); // 中序遍历：后
    }
    int kthSmallest(TreeNode* root, int k) {
        traverse(root,k);
        return res; // 返回结果
    }
};
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def __init__(self):
        self.rank = 0
        self.res=0
    def helper(self,root, k):
        if not root: return
        self.helper(root.left, k)
        self.rank += 1
        if self.rank == k:
            self.res =root.val
            return
        self.helper(root.right, k)
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        self.helper(root,k)
        return self.res

写法2：利用二叉搜索树的框架进行递归

if (root.val == target)
    // 找到目标，做点什么
if (root.val < target) 
    BST(root.right, target);
if (root.val > target)
    BST(root.left, target);
  • 统计root树对应的节点数：每个节点需要记录，以自己为根的这棵二叉树有多少个节点
  • 如果count+1==k，则此时就是要找的结果
  • 如果count+1<k,说明目标值在右子树中
  • 否则在左子树中

在写有返回类型（如函数返回int类型）的if… else语句时，一定要严谨，写成

if
else if
else if
else 或者剩余情况直接return

不要少了最后的else语句（或者return 剩余情况）。否则你以为你都判断了各种情况，但编译器是很严谨的，它并不认为你的if语句都涵盖了各种情况，报错error: non-void function does not return a value in all control paths [-Werror,-Wreturn-type] }

比如，下面的写法就是错误的

int kthSmallest(TreeNode *root, int k) {
    int count = calNode(root->left);
    if (count + 1 == k) {
        return root->val;
    }
    if (count + 1 < k) {
        return kthSmallest(root->right, k - count - 1);
    }
    if (count + 1 > k) {
        return kthSmallest(root->left, k);
    }
    // 编译器就会问：那其余情况呢？怎么没有写出来？
}

可以写成

int kthSmallest(TreeNode *root, int k) {
    int count = calNode(root->left);
//        找到目标，返回结果
    if (count + 1 == k) {
        return root->val;
    } 
    if (count + 1 < k) { // 目标在右子树中
        return kthSmallest(root->right, k - count - 1);
    }
    else { // 目标在左子树中
        return kthSmallest(root->left, k);
    }    
}

// 或者
int kthSmallest(TreeNode *root, int k) {
    int count = calNode(root->left);
//        找到目标，返回结果
    if (count + 1 == k) {
        return root->val;
    } 
    if (count + 1 < k) { // 目标在右子树中
        return kthSmallest(root->right, k - count - 1);
    }
    return kthSmallest(root->left, k); // 涵盖剩余情况 
}
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
//    统计当前root树的节点数
    int calNode(TreeNode *root) {
        if (root == nullptr) return 0;
        int l = calNode(root->left);
        int r = calNode(root->right);
        return l + r + 1;
    }

    int kthSmallest(TreeNode *root, int k) {
        int count = calNode(root->left);
//        找到目标，返回结果
        if (count + 1 == k) {
            return root->val;
        } 
        if (count + 1 < k) { // 目标在右子树中
            return kthSmallest(root->right, k - count - 1);
        }
        else { // 目标在左子树中
            return kthSmallest(root->left, k);
        }
    }
};
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def root_count(self,root):
        if not root:return 0
        l=self.root_count(root.left)
        r=self.root_count(root.right)
        return l+r+1
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        count=self.root_count(root.left)
        current=count+1
        if current==k:
            return root.val
        elif current<k:
            return self.kthSmallest(root.right,k-current)
        else:
            return self.kthSmallest(root.left,k)
  • 其他递归写法
class Solution:
    def __init__(self):
        self.ans = -1
        self.cnt = 0

    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        if not root:
            return self.ans
        self.kthSmallest(root.left, k)
        self.cnt += 1
        if self.cnt == k:
            self.ans = root.val
        self.kthSmallest(root.right, k)
        return self.ans

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

  • 一般地，二叉搜索树进行中序遍历后，可以把数据变为升序排列。本题要算累加树，而且是从最大元素开始遍历，类似于降序排列后的“前缀和”
  • 递归函数traverse()的含义：以逆的中序遍历的方式更新全局的累加和sum，并改变当前节点的值
  • 在递归函数中：
    • 要实现二叉搜索树的降序排列，可进行逆的中序遍历：右、中、左
    • 用一个sum变量更新当前的累加和
    • 根节点需要做的是：更新当前的sum，把当前的sum赋值给根节点
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sum=0;
    void traverse(TreeNode* root){
        if (root == nullptr) return;
        traverse(root->right);
        sum+=root->val;
        root->val=sum;
        traverse(root->left);
    }
    TreeNode* convertBST(TreeNode* root) {
        traverse(root);
        return root;
    }
};
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def helper(self,root):
        if not root: return
        self.helper(root.right)
        self.sum+=root.val
        root.val=self.sum
        self.helper(root.left)

    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        self.sum=0
        self.helper(root)
        return root
赏

   转载规则


《第一章：手把手带你刷二叉搜索树-第一期》 由 M 采用 知识共享署名 4.0 国际许可协议 进行许可。
  目录