树面试题解析｜面试大师

标签题目

树相关面试题

这道题考察扁平数组转树的实现能力。关键不是只会 parentId 挂 children，而是先用 Map 按唯一 id 去重和建索引，再用第二遍挂载，明确重复 id、父节点后出现、多根、孤儿节点和循环引用的处理策略。

随机森林是用多棵决策树做 Bagging 集成的方法，通过样本随机和特征随机降低单棵树的方差，最终用投票或平均得到更稳的预测。

树的遍历要区分深度优先和广度优先，二叉树常见前序、中序、后序，通用树还包括层序和递归/迭代两类实现。

怎么算出二叉树的深度？这道腾讯牛客题的关键是围绕“二叉树深度计算”讲清概念、机制、取舍和边界。二叉树深度可以递归计算：空树深度为 0，非空节点深度为 1 + max(leftDepth, rightDepth)。也可以用 BFS 层序遍历，每处理完一层深度加一。

红黑树的核心性质是什么？这道腾讯牛客题的关键是围绕“红黑树核心性质”讲清概念、机制、取舍和边界。红黑树是近似平衡二叉搜索树，核心性质包括：节点红或黑，根节点黑，所有 NIL 叶子黑，红节点不能有红孩子，从任一节点到所有后代 NIL 叶子的黑节点数相同。

二叉树有哪些基本性质和特点？这道腾讯牛客题的关键是围绕“二叉树基本性质”讲清概念、机制、取舍和边界。二叉树每个节点最多有两个孩子，可分为普通二叉树、满二叉树、完全二叉树、平衡二叉树和二叉搜索树等。常见性质包括第 i 层最多 2^(i-1) 个节点，深度为 h 的二叉树最多 2^h-1 个节点。

平衡二叉树失衡后如何通过旋转恢复平衡？这道腾讯牛客题的关键是围绕“平衡二叉树旋转维护”讲清概念、机制、取舍和边界。平衡二叉树常以 AVL 为例，要求任一节点左右子树高度差不超过 1。插入或删除导致失衡后，根据 LL、RR、LR、RL 四种情况做单旋或双旋恢复平衡。

什么是平衡二叉树，如何实现基本的平衡维护？这道腾讯牛客题的关键是围绕“平衡二叉树旋转维护”讲清概念、机制、取舍和边界。平衡二叉树常以 AVL 为例，要求任一节点左右子树高度差不超过 1。插入或删除导致失衡后，根据 LL、RR、LR、RL 四种情况做单旋或双旋恢复平衡。

决策树分裂准则用于选择让子节点更纯的特征和切分点。信息增益看熵下降，容易偏向取值多的特征；信息增益比用特征自身的分裂信息做归一化，缓解多值特征偏置，但也可能偏向分裂信息过小的特征，需要结合阈值和验证效果判断。