如何判断两个结点是否在一棵树上

Question

如题所述

Answer 1

要判断两个结点是否在一棵树上，可以使用以下方法：
1. 通过父节点来判断：如果两个结点有相同的父节点，那么它们一定在同一棵树上。但是，如果两个结点没有相同的父节点，并不能确定它们是否在同一棵树上。
2. 通过子树来判断：如果一个结点是另一个结点的子节点，那么它们一定在同一棵树上。但是，如果两个结点没有直接的子节点关系，也不能确定它们是否在同一棵树上。
3. 通过路径来判断：如果两个结点之间的路径上所有节点都存在于同一棵树中，那么它们一定在同一棵树上。但是，如果路径上存在任何一个节点不在同一棵树中，就不能确定它们是否在同一棵树上。
因此，要判断两个结点是否在一棵树上，需要综合考虑以上几种因素。如果两个结点之间存在一条路径，并且路径上所有节点都存在于同一棵树中，那么它们一定在同一棵树上。否则，就不能确定它们是否在同一棵树上。

Answer 2

平衡二叉树是指一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，即所有结点，其左右子树高度差不超过1。 判读步骤是： 先计算所有结点的高度，高度是从叶节点开始（其高度为1）自底向上逐层累加的，不同叶子节点计算开始计算时，高度不同取最大值。 然后计算结点左右子树的高度差，如果绝对值都不超过1，就是平衡的。 例子： A / \ B C / \ D E 高度是 D:1 E:1 B:2 C:1 A:3，A的高度差为1， B为0 C为0 叶子结点可以不用计算，肯定为0。上述例子的二叉树就是平衡的二叉树。 看一下例子 A / \ B C / \ D E / F 高度是 F:1 D:2 E:1 B:3 C:1 A:4,其中A的左右子树高度差B3 - A1 = 2，高度差大于2，所以不平衡。 当然实际判断是不是平衡二叉树，不一定需要计算每一个结点高度，因为左子树高一点或者右子树高一点，表面看过去还是比较明显的，计算一下比较明显的几个点就可以。本回答被提问者采纳