用java 编写求一棵二叉树先序遍历的算法程序
时间: 2024-03-11 17:47:11 浏览: 24
以下是用 Java 编写求一棵二叉树先序遍历的算法程序(同样使用递归实现):
```java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
res.add(root.val);
res.addAll(preorderTraversal(root.left));
res.addAll(preorderTraversal(root.right));
return res;
}
}
```
其中,`TreeNode` 是二叉树的节点类,包含值 `val`、左子树 `left`、右子树 `right`。`preorderTraversal` 函数接受根节点 `root`,返回一个列表,表示先序遍历结果。具体实现思路与 Python 版本相同:先访问根节点,再递归访问左子树和右子树。如果根节点为 `null`,直接返回空列表。
相关问题
编写求二叉树先序遍历的算法程序
以下是求二叉树先序遍历的算法程序(使用递归实现):
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorderTraversal(root: TreeNode) -> List[int]:
if not root:
return []
res = [root.val]
res += preorderTraversal(root.left)
res += preorderTraversal(root.right)
return res
```
其中,`TreeNode` 是二叉树的节点类,包含值 `val`、左子树 `left`、右子树 `right`。`preorderTraversal` 函数接受根节点 `root`,返回一个列表,表示先序遍历结果。具体实现思路为:先访问根节点,再递归访问左子树和右子树。如果根节点为 `None`,直接返回空列表。
二叉树先序遍历递归算法
二叉树先序遍历的递归算法如下:
1. 如果二叉树为空,则返回。
2. 访问根节点。
3. 对根节点的左子树进行先序遍历。
4. 对根节点的右子树进行先序遍历。
代码实现如下(假设二叉树的节点类型为Node):
```python
def preorder_traversal(root):
if root:
print(root.val) # 访问根节点
preorder_traversal(root.left) # 先序遍历左子树
preorder_traversal(root.right) # 先序遍历右子树
```
在上述代码中,我们首先判断了二叉树是否为空,如果不为空则依次执行访问根节点、先序遍历左子树、先序遍历右子树的操作。这样递归进行下去,直到遍历完整个二叉树。