二叉树深度优先遍历

二叉树深度优先遍历（Depth-First-Search，DFS）有三种方式：前序遍历、中序遍历和后序遍历。其中，前序遍历先遍历根节点，然后遍历左子树，最后遍历右子树；中序遍历先遍历左子树，然后遍历根节点，最后遍历右子树；后序遍历先遍历左子树，然后遍历右子树，最后遍历根节点。以下是前序遍历的实现代码：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def dfs_preorder(self, root: TreeNode):
        if not root:
            return
        print(root.val)
        self.dfs_preorder(root.left)
        self.dfs_preorder(root.right)

其中，`dfs_preorder`函数为前序遍历函数，使用递归实现。如果当前节点为空，则直接返回；否则，先输出当前节点的值，然后递归遍历左子树和右子树。

相关问题

java 二叉树深度优先遍历

Java实现二叉树的深度优先遍历可以使用递归或者栈来实现。递归方法比较简单，可以按照先序遍历、中序遍历和后序遍历的方式进行深度优先遍历。下面是一段示例代码，演示了Java中使用递归实现深度优先遍历的方法：

public class BinaryTree {

    // 定义二叉树节点类
    public class TreeNode {
        public TreeNode leftNode;
        public TreeNode rightNode;
        public Integer val;

        public TreeNode(Integer val) {
            this.val = val;
        }
    }
    
    // 深度优先遍历-先序遍历
    public void startErgodic(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.print(node.val + " ");
        startErgodic(node.leftNode);
        startErgodic(node.rightNode);
    }

    // 深度优先遍历-中序遍历
    public void midErgodic(TreeNode node) {
        if (node == null) {
            return;
        }
        midErgodic(node.leftNode);
        System.out.print(node.val + " ");
        midErgodic(node.rightNode);
    }

    // 深度优先遍历-后序遍历
    public void endErgodic(TreeNode node) {
        if (node == null) {
            return;
        }
        endErgodic(node.leftNode);
        endErgodic(node.rightNode);
        System.out.print(node.val + " ");
    }
    
    // 二叉树的插入操作
    public void insert(Integer val) {
        // 插入操作的具体实现代码
    }

    // 二叉树的递归插入操作
    public void insertDigui(Integer val, TreeNode node) {
        // 递归插入操作的具体实现代码
    }

    // 广度优先遍历
    public void Order() {
        // 广度优先遍历的具体实现代码
    }
}

public class Test {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        // 创建二叉树并进行插入操作
        
        // 深度优先遍历-先序遍历
        binaryTree.startErgodic(binaryTree.root);
        System.out.println();
        // 深度优先遍历-中序遍历
        binaryTree.midErgodic(binaryTree.root);
        System.out.println();
        // 深度优先遍历-后序遍历
        binaryTree.endErgodic(binaryTree.root);
    }
}

上述代码中的`startErgodic()`方法实现了二叉树的深度优先遍历先序遍历，`midErgodic()`方法实现了中序遍历，`endErgodic()`方法实现了后序遍历。可以根据需要选择相应的方法进行遍历。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [Java实现二叉树的深度优先遍历和广度优先遍历算法示例](https://download.csdn.net/download/weixin_38518885/12761000)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
- *2* *3* [java有序二叉树的深度优先遍历和广度优先遍历](https://blog.csdn.net/m566666/article/details/122280365)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]

数据结构二叉树深度优先遍历

二叉树的深度优先遍历是一种遍历二叉树的方法，它按照根节点、左子树、右子树的顺序进行遍历。深度优先遍历有三种方式：前序遍历、中序遍历和后序遍历。

1. 前序遍历（Preorder Traversal）：先访问根节点，然后递归地遍历左子树和右子树。
2. 中序遍历（Inorder Traversal）：先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。
3. 后序遍历（Postorder Traversal）：先递归地遍历左子树和右子树，最后访问根节点。

下面是三种深度优先遍历的示例代码：

1. 前序遍历：

def preorderTraversal(root):
    if root is None:
        return []
    result = []
    result.append(root.val)
    result.extend(preorderTraversal(root.left))
    result.extend(preorderTraversal(root.right))
    return result

2. 中序遍历：

def inorderTraversal(root):
    if root is None:
        return []
    result = []
    result.extend(inorderTraversal(root.left))
    result.append(root.val)
    result.extend(inorderTraversal(root.right))
    return result

3. 后序遍历：

def postorderTraversal(root):
    if root is None:
        return []
    result = []
    result.extend(postorderTraversal(root.left))
    result.extend(postorderTraversal(root.right))
    result.append(root.val)
    return result