Loading... ## 复习题7  $$ ASL = \frac {1+2\times 2 + 3\times 3 + 3\times 4 + 5\times 2 + 6}{12} = \frac {42}{12} = \frac {7}{2} $$ ## 算法题1 > **在接下来的两道题目中,我们假设二叉树结点的数据结构表示为如下代码** ```cpp /** * 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) {} * }; */ ``` * 参考的搜索代码: ```cpp int get_node_deep(TreeNode* now,TreeNode* target,int deep) { // 找到目标,返回深度 if(now == target) return deep; // 如果当前节点值大于目标节点,且左子树存在,则我们向树的左边搜索 if(now -> val > target -> val && now->left != nullptr) return get_node_deep(now->left,target,deep+1); // 如果当前节点值小于目标节点,且右子树存在,则我们向树的右边搜索 if(now -> val < target -> val && now -> right != nullptr) return get_node_deep(now->right,target,deep+1); // 都不存在返回错误码 -1 return -1; } ``` ## 算法题2 * 解析: > 因为是寻找二叉搜索树中节点的<a href = "https://zh.wikipedia.org/zh-cn/%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88_(%E5%9B%BE%E8%AE%BA)">最近公共祖先(LCA)</a>,根据二叉搜索树的性质,两个节点(假设两个节点的值为$a$和$b$)的LCA即从根节点查找,节点值第一个满足: $$ min(a,b) \le val \le max(a,b) $$ > 的节点 * 参考代码(这里我们假设$(*a).val < (*b).val$): ```cpp TreeNode* get_bst_lca(TreeNode* now,TreeNode* a,TreeNode* b) { // 当前节点值小于a,b 则向左搜索 if(now -> val < a->val) return get_bst_lca(now -> right,a,b); // 当前节点值大于a,b 则向右搜索 if(now -> val > b->val) return get_bst_lca(now -> left,a,b); // 满足条件,返回答案 return now; } ``` Last modification：May 24, 2022 © Allow specification reprint Support Appreciate the author Like 5 如果觉得我的文章对你有用，请随意赞赏