树的深度优先遍历java回溯算法

以下是Java中树的深度优先遍历回溯算法的示例代码：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    public void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.println(root.val); // 先访问根节点
        dfs(root.left); // 再访问左子树
        dfs(root.right); // 最后访问右子树
    }
}

在这个示例中，我们定义了一个`TreeNode`类来表示树的节点。`dfs`方法采用递归的方式实现深度优先遍历，首先访问根节点，然后递归访问左子树和右子树。

相关问题

dfs深度优先遍历 java

深度优先搜索（DFS）是一种常用的图遍历算法，它可以用来遍历或搜索图中的节点。在DFS中，从一个起始节点开始，沿着一条路径尽可能深入地访问节点，直到无法继续深入为止，然后回溯到上一个节点，继续访问其他未被访问的节点，直到所有节点都被访问为止。

在Java中，可以使用递归或者栈来实现DFS算法。下面是一个使用递归实现DFS的示例代码：

import java.util.*;

class Graph {
    private int V; // 图中节点的数量
    private LinkedList<Integer> adj[]; // 邻接表表示图

    // 构造函数
    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    // 添加边
    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    // 递归实现DFS
    void DFSUtil(int v, boolean visited[]) {
        visited[v] = true;
        System.out.print(v + " ");

        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }

    // 对外公开的DFS接口
    void DFS(int v) {
        boolean visited[] = new boolean[V];
        DFSUtil(v, visited);
    }
}

public class Main {
    public static void main(String args[]) {
        Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("节点2开始的DFS遍历结果：");
        g.DFS(2);
    }
}

上述代码中，我们首先定义了一个`Graph`类来表示图，其中使用邻接表来存储图的结构。然后，我们实现了`DFSUtil`方法来递归地进行DFS遍历，并在遍历过中打印节点的值。最后，在`main`方法中创建一个图对象，并调用`DFS`方法来进行DFS遍历。

深度优先搜索遍历 java

深度优先搜索（Depth First Search，简称DFS）是一种用于遍历或搜索树或图数据结构的算法。在Java中，我们可以使用递归或栈来实现深度优先搜索。以下是简单的深度优先搜索遍历步骤：

1. **选择一个起始节点**：通常从根节点开始，或者任意未访问过的节点。

2. **标记当前节点为已访问**：将其设置为已访问状态，防止重复访问。

3. **访问当前节点**：对当前节点执行所需的操作，如打印节点值。

4. **递归或循环展开**：对于当前节点的所有邻接节点，如果它们还未访问过，就进行下一步操作，即进入下一个邻接节点并重复上述过程。

5. **回溯**：当所有可达的节点都访问过后，返回上一层，继续处理其他分支，直到整个图或树都被访问完。

下面是一个基本的递归版DFS遍历Java代码示例（假设有一个无向图表示为邻接列表）：

import java.util.*;

public class DFS {
    private boolean[] visited; // 记录节点是否已访问

    public void dfs(int node, List<Integer>[] graph) {
        visited[node] = true;
        System.out.println(node); // 打印当前节点
        for (int neighbor : graph[node]) { // 遍历邻居
            if (!visited[neighbor]) {
                dfs(neighbor, graph);
            }
        }
    }

    public static void main(String[] args) {
        int[][] graph = {{1, 2}, {2, 3}, {3, 4}};
        DFS dfs = new DFS();
        visited = new boolean[5]; // 初始化所有节点未访问
        dfs.dfs(1, convertAdjListToArray(graph)); // 使用递归从1开始
    }

    private static List<Integer>[] convertAdjListToArray(int[][] graph) {
        int size = graph.length;
        List<Integer>[] adjList = new ArrayList[size];
        for (int i = 0; i < size; i++) {
            adjList[i] = new ArrayList<>();
            for (int j = 0; j < graph[i].length; j++) {
                if (graph[i][j] != -1) {
                    adjList[i].add(graph[i][j]);
                }
            }
        }
        return adjList;
    }
}