Skip to content
TheChatArchiveThe Chat Archive
gpt-4-0314· OpenAIAi2 WildChat-4.8M (AI2)

用Java语言实现前序遍历

  1. User

    用Java语言实现前序遍历

  2. Assistant

    前序遍历是指先访问根节点,然后依次访问左子树和右子树。这里我们使用递归的方式实现前序遍历。

    首先我们定义一个二叉树类 TreeNode:

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    
        TreeNode() {
        }
    
        TreeNode(int val) {
            this.val = val;
        }
    
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    

    然后创建一个 PreorderTraversal 类,实现前序遍历的方法:

    import java.util.ArrayList;
    import java.util.List;
    
    public class PreorderTraversal {
    
        public static void main(String[] args) {
            TreeNode root = new TreeNode(1);
            root.left = new TreeNode(2);
            root.right = new TreeNode(3);
            root.left.left = new TreeNode(4);
            root.left.right = new TreeNode(5);
    
            List<Integer> result = preorderTraversal(root);
            System.out.println(result);
        }
    
        public static List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> result = new ArrayList<>();
            preorder(root, result);
            return result;
        }
    
        private static void preorder(TreeNode node, List<Integer> result) {
            if (node == null) {
                return;
            }
    
            // 访问当前节点
            result.add(node.val);
    
            // 递归访问左子树
            preorder(node.left, result);
    
            // 递归访问右子树
            preorder(node.right, result);
        }
    }
    

    这个程序首先创建了一个二叉树,并调用 preorderTraversal 方法前序遍历,输出结果。

    注意:这里我们使用了递归,也可以使用迭代的方式实现,这需要使用栈来辅助。

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.