DS二叉树—二叉树结点的最大距离
时间: 2023-11-12 17:06:31 浏览: 83
DS二叉树中,二叉树结点的最大距离是指所有结点间距离的最大值。具体来说,可以通过先序遍历顺序创建二叉树,并使用递归的方式计算出二叉树结点的最大距离和最大距离的两个结点。其中,最大距离的计算可以通过递归计算左右子树的最大深度和最大距离来实现。而最大距离的两个结点可以通过递归计算左右子树的最大深度和最大距离,并比较左右子树的最大距离来确定。
相关问题
java二叉树寻找兄弟结点
要寻找二叉树中某个结点的兄弟结点,需要先找到该结点的父节点,然后再找到父节点的另一个子结点即可。
实现代码如下:
```java
public TreeNode findSibling(TreeNode root, TreeNode node) {
if (root == null || node == null || root == node) {
return null;
}
TreeNode parent = getParent(root, node);
if (parent == null) {
return null;
}
if (parent.left == node) {
return parent.right;
} else {
return parent.left;
}
}
private TreeNode getParent(TreeNode root, TreeNode node) {
if (root == null || root == node) {
return null;
}
if (root.left == node || root.right == node) {
return root;
}
TreeNode parent = getParent(root.left, node);
if (parent != null) {
return parent;
}
return getParent(root.right, node);
}
```
其中,`findSibling` 方法接受二叉树的根结点和目标结点作为参数,返回目标结点的兄弟结点。该方法先调用 `getParent` 方法找到目标结点的父节点,然后根据父节点的左右子结点来找到目标结点的兄弟结点。
`getParent` 方法用于找到目标结点的父节点。该方法递归地从根结点开始向下遍历二叉树,直到找到目标结点的父节点为止。如果没有找到父节点,返回 `null`。
二叉树的叶子结点个数
二叉树的叶子结点是指没有子节点的节点,因此计算二叉树的叶子结点个数需要遍历整棵树并统计叶子结点的数量。可以使用递归或迭代的方式实现遍历,以下是两种常见的实现方式:
1. 递归实现
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def count_leaf_nodes(root: TreeNode) -> int:
if not root:
return 0
if not root.left and not root.right:
return 1
return count_leaf_nodes(root.left) + count_leaf_nodes(root.right)
```
2. 迭代实现
```python
def count_leaf_nodes(root: TreeNode) -> int:
if not root:
return 0
stack = [root]
count = 0
while stack:
node = stack.pop()
if not node.left and not node.right:
count += 1
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return count
```