算法笔记_面试题_16. 二叉树相关_模板及示例十几道

目录

1. 基本概念

1.1 常考二叉树种类

1.2 二叉树的存储

1.3 遍历方式(贯穿整个leecode常考题目)

1.4 二叉树的定义

 2. 相关题目

2.1 树的3种遍历（模板）

例1. 二叉树的前中后序遍历_递归版_traverse法

例2. 二叉树的前中后序遍历_递归版_分治法（用于理解分治）

例3. 二叉树的前中后序遍历_非递归版_使用栈（推荐）

2.2 树的深度相关

例4. 二叉树的最大深度

例5. 判断是否是平衡二叉树

例6. 最近公共祖先 LCA（经典题目）

例7. 二叉树最大路径和_从根节点出发

例8. 二叉树最大路径和_从任意节点出发

2.3 宽度优先遍历 BFS

例9. 二叉树宽度（广度）优先遍历_自顶向下

例10. 二叉树宽度（广度）优先遍历_自低向上

2.3 二叉搜索树 BST

例11. 判断是否是二叉搜索树

例12. 判断节点是否在二叉搜索树中

例13. 找二叉树中指定节点的中序遍历的后继节点

例14. 返回二叉搜索树当前最小值的迭代器

例15. 在二叉搜索树中找指定范围的值，并升序输出到数组中

例16. 在二叉查找树中插入节点

1. 基本概念

参考: 代码随想录 carl；九章算法； leecode； lintcode

1.1 常考二叉树种类

面试中常考的关于二叉树的种类有以下4种:

满二叉树: 每个节点的孩子节点要么是0个, 要么是2个. 也可以说深度为k，有2^k-1个节点的⼆叉树。

完全二叉树: 满二叉树, 若要是缺少节点,只能是从右往左缺.

  二叉搜索树: 所有的节点的左子节点到大于右子节点的值.

平衡二叉搜索树: 二叉搜索树中, 所有节点的左子树的深度 - 右子数的深度 val); //行1 traverse(root->left, result); //行2 traverse(root->right, result);//行3 } }; // inorder: 行2-行1-行3 // postorder：行2-行3-行1 例2. 二叉树的前中后序遍历_递归版_分治法（用于理解分治）

分治法，一般函数的返回值与要求的一致，不用添加辅助函数（或者称为helper函数）。将问题拆分为更小子问题（把参数变小往下走），只用考虑单层的逻辑（该逻辑适用于子问题的求解）。

C++/C--多个vector拼接的方法【转载】_Jensen Lee的博客-CSDN博客_c++ 拼接vector

    vector preorderTraversal(TreeNode* root) {
        vector result;
        if (!root) {
            return result;
        }
        vector left = preorderTraversal(root->left);
        vector right =preorderTraversal(root->right);

        result.push_back(root->val);    //行1
        result.insert(result.end(), left.begin(), left.end()); //行2
        result.insert(result.end(), right.begin(), right.end());//行3

        return result;
    }

    // inorder: 行2-行1-行3
    // postorder：行2-行3-行1

上述两种方式的对比：

递归三要素：

• 函数定义；
• 出口（返回值）；
• 拆分为更小子问题的处理流程（把参数变小往下走）。

对比traverse 和 Divide&Conquer方法：

• traverse 一般是游走，没有返回值，把要的结果放入参数中；
• DC方法一般有返回值，函数的定义跟要求的签名是一致的。

例3. 二叉树的前中后序遍历_非递归版_使用栈（推荐）

还可参考 算法笔记_面试题_4.树的遍历(前序/中序/后续遍历）

前序_栈实现

    vector preorderTraversal(TreeNode* root) {
        vector result;
        stack stk;
        if (root == nullptr) {
            return result;
        }
        stk.push(root);     //先把根节点入栈
        while (!stk.empty()) {
            TreeNode* cur = stk.top(); //只要栈非空，就取出栈顶元素
            stk.pop(); 
            if (cur == nullptr) {
                continue;
            }
            result.push_back(cur->val); //处理
            stk.push(cur->right);       // 因为是栈，所以入栈顺序先右后左
            stk.push(cur->left);
        }

        return result;
    }

中序_栈实现（重点记忆）

先定义当前节点指向root节点，然后进入while循环中，只要当前节点不为空或者栈不为空，就不退出while循环。在while循环内部，一直向左子树走，边走边入栈，直到左子树为空，开始出栈，边出栈，变处理节点（即放入结果数组），同时向右子树走....  注意：while条件，第一步是定义一个cur, 而不是先入栈根节点。

    vector inorderTraversal(TreeNode* root) {
        vector result;
        stack stk;

        TreeNode* cur = root; //注意：中序不是先放root入栈，而是定义一个current节点，在while循环中依次入栈
        while (cur != nullptr || !stk.empty()) {
            if (cur != nullptr) { //注意：这里cur是变化的，不能少了非空判断！
                stk.push(cur);    // 注意：依次入栈，《访问节点》，一路向左
                cur = cur->left;
            } else {
                cur = stk.top();
                stk.pop();        //左没了，就开始出栈，
                result.push_back(cur->val); // 《处理节点》
                cur = cur ->right; //指向右，看右有没节点
            }
        }

        return result;
    }

后序_栈实现

基本等价于前序遍历，只是入栈顺序有所变换（访问顺序：根-入左-入右，结果成：根右左），然后颠倒一下成（左右根）

    vector postorderTraversal(TreeNode* root) {
        vector result;
        stack stk;
        if (!root) {
            return result;
        }
        stk.push(root); //依然像前序遍历一样，先将根入栈
        while (!stk.empty()) {
            TreeNode* cur = stk.top(); //取出栈顶元素
            stk.pop();
            if (!cur) continue;
            result.push_back(cur->val); //
            stk.push(cur->left);  //注意这里是先左入栈，后右入栈，所以访问顺序是 根-右-左
            stk.push(cur->right);
        }

        reverse(result.begin(), result.end()); //使用系统函数，颠倒一下顺序成为 左-右-根
        return result;

    }

2.2 树的深度相关 例4. 二叉树的最大深度

描述

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。leecode 104. 二叉树的最大深度

示例：

给定二叉树 [3,9,20,null,null,15,7]，

    3    / \   9  20     /  \    15   7 返回它的最大深度 3 。

代码

traverse法：定义result全局变量（更严格说是类的成员变量），递归参数选择 当前深度curDepth！

class Solution {
public:
    int result;
    int maxDepth(TreeNode* root) {
        result = 0;
        traverse(root, 1); //注意这里 current depth 直接传入1，若为空直接返回递归，结果为0。
        return result;
    }
    void traverse(TreeNode* root, int curDepth) { //注意：传入的是当前深度，值传递
        if (root == nullptr) {
            return;
        }

        if (result < curDepth) { //注意：使用成员变量保存最终的结果
            result = curDepth;
        }
        
        traverse(root->left, curDepth + 1); //注意：递归时，直接作处理，深度+1
        traverse(root->right,curDepth + 1); // 或者在单层逻辑汇总作处理，如下所示，注意++在 if(result 之后！

        //++curDepth;
        //traverse(root->left, curDepth);
        //traverse(root->right,curDepth);
    }
};

分治法：简洁！

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }

        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        
        return max(left,right) + 1;
    }
};

例5. 判断是否是平衡二叉树

描述

给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。leecode 110. 平衡二叉树

示例 1：

输入：root = [3,9,20,null,null,15,7] 输出：true

代码（分治法）

定义一个全局的布尔变量 bBalanced，来更新是否是平衡的。直接使用 求二叉树的最大深度函数。

class Solution {
public:
    bool bBalanced;
    bool isBalanced(TreeNode* root) {
        bBalanced = true;
        maxDepth(root);
        return bBalanced;
    }

    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }

        int left  = maxDepth(root->left);
        int right = maxDepth(root->right);
        
        if (abs(left - right) > 1) { // 相比求二叉树最大深度，只多了此段代码
            bBalanced = false;
        }

        return max(left, right) + 1;
    }
};

剪枝优化：只要一个分支不平衡就直接返回 -1 ，不再判断另一个分支。

class Solution {
public:
    bool bBalanced;
    
    bool isBalanced(TreeNode* root) {
        bBalanced = true;
        maxDepth(root);       
        return bBalanced;
    }

    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }

        int left = maxDepth(root->left);
        if (left == -1 ) {
            bBalanced = false;
            return -1;
        }

        int right = maxDepth(root->right);
        if (right == -1 ) {
            bBalanced = false;
            return -1;
        }

        if (std::abs(left - right) > 1) {
            bBalanced = false;
            return -1; 
        }
        
        return max(left, right) + 1;
    }
};

例6. 二叉树中两个节点的最近公共祖先 LCA（经典题目）

描述 ：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” leecode 236. 二叉树的最近公共祖先

示例 1： 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1    输出：3               解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

有parent指针版：lintcode 474 · 最近公共祖先 II

思路：求各自路径，倒序访问路径，分叉的地方的父节点，就是公共祖先。

/**
 * Definition of ParentTreeNode:
 * class ParentTreeNode {
 * public:
 *     int val;
 *     ParentTreeNode *parent, *left, *right;
 * }
 */
class Solution {
public:
    ParentTreeNode * lowestCommonAncestorII(ParentTreeNode * root, ParentTreeNode * A, ParentTreeNode * B) {
        // write your code here
        vector pathA =  getPath2Root(A);
        vector pathB =  getPath2Root(B);
        reverse(pathA.begin(), pathA.end());
        reverse(pathB.begin(), pathB.end());

        ParentTreeNode * result = nullptr; //该写法可以cover 空树，没有公共祖先，互为父子节点的情况，虽然多次为result赋值。
        for (int i = 0; i < min(pathA.size(), pathB.size()); ++i) {
            if (pathA[i] == pathB[i]) {
                result = pathA[i];            
            } else {
                break;
            }
        }

        return result;
    }

    vector getPath2Root(ParentTreeNode * root) {
        vector result;
        
        ParentTreeNode * cur = root;
        while (cur != nullptr) { //别写成了while(!cur) 错误！
            result.push_back(cur);
            cur = cur->parent;
        }

        return result;
    }
};

无parent指针版：leecode 236. 二叉树的最近公共祖先 =  lintcode 88 · 最近公共祖先 （重点记忆！）

分治法：

• 若当前节点等于其中一个节点，就返回这个节点
• 分治：在当前层中，递归地在左子树找一个节点left，在右子树找一个节点right：
  • left right 都存在，返回当前节点（即当前节点就是最近公共祖先）
  • 否则，谁存在，返回谁
  • 都不存在，返回空

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr || root == p || root == q) {
            return root;
        }

        TreeNode * left  = lowestCommonAncestor(root->left, p, q);
        TreeNode * right = lowestCommonAncestor(root->right, p, q);

        if (left != nullptr && right != nullptr) {
            return root;
        }
        if (left != nullptr) {
            return left;
        }
        if (right != nullptr) {
            return right;
        }

        return nullptr;
    }
};

例7. 二叉树最大路径和_从根节点出发

描述：给定一棵二叉树，找到二叉树的最大路径和，路径必须从根节点出发。路径可在任意节点结束，但至少包含一个节点（也就是根节点）。来源：lintcode 475 · 二叉树的最大路径和 II

样例 1:

输入: {1,2,3}
输出: 4
解释: 
    1
   / \
  2   3
1+3=4

样例 2:

输入: {1,-1,-1}
输出: 1
解释:
    1
   / \
  -1 -1 

代码

分治法是最好的解决方式：最大值 = 当前节点值 + 左右子树中的最大的。

特别注意：当左右子树的结果小于0时，上式需要舍弃（或者+0）

class Solution {
public:
    int maxPathSum2(TreeNode * root) {
        if (root == nullptr) {
            return 0;
        }

        int left = maxPathSum2(root->left);
        int right = maxPathSum2(root->right);
        
        return root->val + max(0,max(left,right)); //特别注意：这里若子节点中最大的还mMaxPath;
        delete result;
        return max;
    }

    ResultType* helper(TreeNode* root) {
        if (root == nullptr) {
            return new ResultType(0, INT_MIN); //注意这里只能是 (0, int最小),因为singlePath后面有+root->val的可能，不能定义成(int最小，xx),会越界
        }

        ResultType* left  = helper(root->left);
        ResultType* right = helper(root->right);

        // 特别注意：singlePath的求解过程，需要与0比较，因为小于0则取0，相当于不要该分支
        int singlePath = max(0, max(left->mSinglePath,right->mSinglePath)) + root->val;
        singlePath = max(0, singlePath); //注意：不能少，singlePath是取根节点到子节点不拐弯路径（深度方向）中的最大者。

        // 特别注意：maxPath的求解过程，不需要跟0比较，因为作为最终结果，有可能就是小于0，比如根左右(-1,0,0)
        int maxPath = max(left->mMaxPath, right->mMaxPath); //比较3种情况，取最大者
        maxPath = max(maxPath, left->mSinglePath + right->mSinglePath + root->val); //这里要将当前root节点作为“拐点”，所以当前root对应的子节点left right只能取singlePath(深度方向路径)了，不然这路径就连接不到一起了。
        
        delete left;
        delete right;
        return new ResultType(singlePath, maxPath); //注意：返回值不要忘了
    }
};

图解说明：

2.3 宽度优先遍历 BFS 例9. 二叉树宽度（广度）优先遍历_自顶向下

描述： 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。 来源：lintcode 69 · 二叉树的层次遍历 = leecode 102. 二叉树的层序遍历

示例： 二叉树：[3,9,20,null,null,15,7],

    3    / \   9  20     /  \    15   7 返回其层序遍历结果：[[3], [9,20],[15,7]]

代码

一个队列的方法（重要，会背！基本所有的宽搜都这么写）

采用队列实现，注意返回值每一层放入一个数组中，返回的是二维数组，所以技巧来了，访问一个元素就弹出一个元素，弹出同时加入子节点。这样以来，访问队列时当前队列中的元素个数，正好等于每一层的元素数量。

class Solution {
public:
    vector levelOrder(TreeNode* root) {
        vector result;
        if (root == nullptr) {
            return result;
        }

        queue que;
        que.push(root); //先放入根节点
        while (!que.empty()) {
            vector curLevel;
            int count = que.size(); //注意：巧妙！逐层遍历，这里队列中的size就是每层元素的个数！
            for (int i = 0; i < count; i++){
                TreeNode * cur = que.front(); //for循环中每次取出一个队列头元素
                que.pop();

                curLevel.push_back(cur->val); //放入当前层的结果数组中
                if (cur->left) que.push(cur->left); //若当以前节点的子节点存在则入队列，进入下一层的while遍历中
                if (cur->right) que.push(cur->right);
            }
            result.push_back(curLevel);
        }

        return result;
    }
};

拓展（只需要知道，理解，面试出现的概率极其少）：

面试官问：能不能用DFS（深度优先遍历）的方式，写下BFS?

答：迭代搜索法：设定一个限制，然后逐渐放宽这个限制。

优点： DFS比BFS节省内存空间的，不需要把所有节点都放入栈中，在原来内存较小年代时常用的方法。

代码：（来自 九章算法）

例10. 二叉树宽度（广度）优先遍历_自低向上

描述：给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历） 来源：lintcode 70 · 二叉树的层次遍历 II = leecode 107. 二叉树的层序遍历 II

代码：

无它，自底向上的遍历，等同于自顶向下的遍历的结果颠倒一下，即只需要在例9返回结果前加一句即可。（前提，二维数组存储的，只颠倒第一维的顺序即可）

...
reverse(result.begin(), result.end());
return result;

2.3 二叉搜索树 BST

人们常说：二叉搜索树有一条非常非常重要性质： 二叉搜索树的中序遍历是升序序列！！！。那这条性质怎么出题，怎么使用呢？

例11. 判断是否是二叉搜索树

描述：给定一个二叉树，判断它是否是合法的二叉查找树(BST)

一棵BST定义为：

• 节点的左子树中的值要严格小于该节点的值。
• 节点的右子树中的值要严格大于该节点的值。
• 左右子树也必须是二叉查找树。
• 一个节点的树也是二叉查找树。

样例

输入：tree = {-1}

输出：true

解释：二叉树如下(仅有一个节点）: -1  这是二叉查找树。

代码（traverse版本） （重点记忆）：

class Solution {
public:
    bool isFirstNode = true; //注意：处理第一个节点时的方法
    int last = INT_MIN;
    bool isValidBST(TreeNode * root) {
        if (root == nullptr) {
            return true;
        }

        if (!isValidBST(root->left)) {               //左
            return false;
        }

        if (!isFirstNode && last >= root->val) {     //根
            return false;
        } else {                  //只为第一个节点,或者满足二叉搜索树规律的节点执行
            isFirstNode = false;
            last = root->val;
        }

        if (!isValidBST(root->right)) {              //右
            return false;
        }

        return true;
    }
};

例12. 判断节点是否在二叉搜索树中

简单题 : 700. 二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。 

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr) {
            return nullptr;
        }
        if (root->val == val) {
            return root;
        } else if (val < root->val) {
            return searchBST(root->left, val);
        } else {
            return searchBST(root->right, val);
        }
    }
};

例13. 找二叉树中指定节点的中序遍历的后继节点

描述

        给定一棵二叉搜索树和其中的一个节点 p ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。节点 p 的后继是值比 p.val 大的节点中键值最小的节点，即按中序遍历的顺序节点 p 的下一个节点。 （来源：leecode 剑指 Offer II 053. 二叉搜索树中的中序后继

 = lintcode 448 · 二叉查找树的中序后继 ，中等题）

代码 (重点理解)

若目标节点的值 < 当前节点，那中序后继要么在左子树中，要么就是根节点； 若目标节点的值 >= 当前节点，那中序后继只可能在右子树中，直接返回右子树的递归结果即可。

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if (root == nullptr) {
            return nullptr;
        }
        if (p->val < root->val) {
            TreeNode* left = inorderSuccessor(root->left, p);
            return left ? left : root;
        } else {
            return inorderSuccessor(root->right, p);
        }
    }
};

例14. 返回二叉搜索树当前最小值的迭代器

描述: 设计实现一个带有下列属性的二叉查找树的迭代器：next()返回BST中下一个最小的元素.（来源： lintcode 86 · 二叉查找树迭代器）(级别：困难， 其实不难)

• 元素按照递增的顺序被访问（比如中序遍历）
• next()和hasNext()的询问操作要求均摊时间复杂度是O(1)O(1)

样例 1：

输入

tree = {10,1,11,#,6,#,12}

输出：

[1,6,10,11,12]

解释：

二叉查找树如下 : 10 /   \ 1     11 \       \ 6       12 可以返回二叉查找树的中序遍历 [1,6,10,11,12]

代码

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 * Example of iterate a tree:
 * BSTIterator iterator = BSTIterator(root);
 * while (iterator.hasNext()) {
 *    TreeNode * node = iterator.next();
 *    do something for node
 */
class BSTIterator {
public:
    /*
    * @param root: The root of binary tree.
    */
    stack stk;
    TreeNode * cur;
    BSTIterator(TreeNode * root) {
        // do intialization if necessary
        cur = root;
    }

    /*
     * @return: True if there has next node, or false
     */
    bool hasNext() {
        // write your code here
        return (cur != nullptr || !stk.empty()); //注意：满足其一即可，因为cur在找next过程中有可能为空
    }

    /*
     * @return: return next node
     */
    TreeNode * next() {
        // write your code here
        while (cur != nullptr) { // 左子树一直入栈，直到为空
            stk.push(cur);
            cur = cur->left;
        }

        cur = stk.top();        
        stk.pop();
        TreeNode * res = cur;   // 栈顶元素即为当前最小值
        cur = cur->right;       // 特别注意：取出当前最小值后，更新当前缓冲指向的值为当前节点的右子节点
        
        return res;
    }
};

例15. 在二叉搜索树中找指定范围的值，并升序输出到数组中

描述：给定一个二叉查找树和范围[k1, k2]。按照升序返回给定范围内的节点值。（来源：lintcode 11 · 二叉查找树中搜索区间）

样例 1：

输入：

tree = {20,8,22,4,12}
k1 = 10
k2 = 22

输出：

[12,20,22]

解释：[12,20,22]介于10和22之间

代码

• 1). 中序遍历模板，符合条件的就放入数组；
• 2). 因为是二叉搜索树（中序遍历是升序），所以找到一个大于上界的就可以剪枝，直接返回，不需要再继续遍历。

class Solution {
public:
    vector searchRange(TreeNode * root, int k1, int k2) {
        // write your code here
        vector result;
        traverse(root, result, k1, k2);
        return result;

    }
    void traverse(TreeNode* root, vector & result, int k1, int k2) {
        if (root == nullptr) {
            return;
        }
        
        traverse(root->left, result, k1, k2);
        
        if (root->val >= k1 && root->val val);
        }
        if (root->val > k2) { //中序是升序，可以在这里剪枝
            return;
        }
        
        traverse(root->right, result, k1, k2);
    }
};

例16. 在二叉查找树中插入节点

描述：给定一棵二叉查找树和一个新的树节点，将节点插入到树中。你需要保证该树仍然是一棵二叉查找树。题目保证不会出现重复的值。（来源：lintcode 85 · 在二叉查找树中插入节点  约等于 leecode 701. 二叉搜索树中的插入操作 ）

样例 1：

输入：

tree = {}
node= 1

输出：

{1}

解释：在空树中插入一个点，应该插入为根节点。

样例 2：

输入：

tree = {2,1,4,#,#,3}
node = 6

输出：

{2,1,4,#,#,3,6}

代码1：有点类似分治法：

• 若当前节点为空，则说明找到了正确的位置，直接返回目标节点即可；
• 若目标节点的值 < 当前节点的值，则肯定在左子树插入，（分治法：假设下一层的插入已完成）将插入结果连接到当前节点的左子树上；
• 否则，则肯定在右子树插入，同理进行连接；
• 别忘了返回 root (当前节点)。

class Solution {
public:
    TreeNode * insertNode(TreeNode * root, TreeNode * node) {
        if (root == nullptr) {
            return node;
        }

        if (node->val < root->val) {
            root->left  = insertNode(root->left,  node);  //左子树更新后还接在左子树
        } else {
            root->right = insertNode(root->right, node);  //右子树更新后还接在右子树
        }
        
        return root;  //注意：别忘了返回root
    }
};

代码2：traverse方法（引用传递）

• 情况1：当插入节点的值当前节点，向右遍历，
• 若当前节点为空，将当前节点指向插入节点。此时的当前节点即为上一层情况1中的“当前节点”的左子节点，或者上一层情况2中“当前节点”的右子节点。

    TreeNode * insertNode(TreeNode * root, TreeNode * node) {
        traverse(root, node);
        return root;
    }

    void traverse(TreeNode * &root, TreeNode * node) { //特别注意：这里是引用传递
        if (root == nullptr) {
            root = node;
            return;
        }

        if (node->val < root->val) {
            traverse(root->left, node);
        } else {
            traverse(root->right, node);
        }
    }