怎么输出二叉树中从每个叶子结点到根节点的路径
时间: 2024-05-09 17:01:51 浏览: 11
输出二叉树中从每个叶子结点到根节点的路径可以通过深度优先搜索算法实现。具体步骤如下:
1. 定义一个栈来存储路径,从根节点开始进行深度优先搜索遍历二叉树。
2. 遍历到叶子节点时,将栈中的路径输出即可。
3. 遍历完一个子树后,需要将栈顶元素弹出,回溯到上一层继续搜索。
以下是Java代码实现:
```java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public List<List<Integer>> binaryTreePaths(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Stack<Integer> stack = new Stack<>();
dfs(root, stack, res);
return res;
}
private void dfs(TreeNode node, Stack<Integer> stack, List<List<Integer>> res) {
stack.push(node.val);
if (node.left == null && node.right == null) {
res.add(new ArrayList<>(stack));
} else {
if (node.left != null) {
dfs(node.left, stack, res);
}
if (node.right != null) {
dfs(node.right, stack, res);
}
}
stack.pop();
}
}
```
该算法的时间复杂度为O(n),其中n为二叉树中节点的个数。