先序遍历二叉树java

二叉树的先序遍历是指先访问根节点，然后访问左子树，最后访问右子树。下面是Java实现二叉树先序遍历的代码：

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        res.add(node.val);
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
    return res;
}

这里使用了栈来模拟递归过程，先将根节点入栈，然后每次取出栈顶元素，将其值加入结果列表中，并将其右子节点和左子节点依次入栈。由于栈是后进先出的，所以先将右子节点入栈，再将左子节点入栈，这样在取出栈顶元素时就可以先访问左子树，再访问右子树，从而实现先序遍历。

相关问题

java先序遍历构造二叉树

以下是Java代码，使用递归实现先序遍历构造二叉树：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int preLen = preorder.length;
        int inLen = inorder.length;
        // 构建二叉树
        return buildTreeHelper(preorder, 0, preLen - 1, inorder, 0, inLen - 1);
    }

    private TreeNode buildTreeHelper(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            // 递归终止条件
            return null;
        }
        // 先序遍历的第一个节点为根节点
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);
        // 在中序遍历中找到根节点的位置
        int rootIndex = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                rootIndex = i;
                break;
            }
        }
        // 递归构建左右子树
        int leftSubtreeSize = rootIndex - inStart;
        root.left = buildTreeHelper(preorder, preStart + 1, preStart + leftSubtreeSize, inorder, inStart, rootIndex - 1);
        root.right = buildTreeHelper(preorder, preStart + leftSubtreeSize + 1, preEnd, inorder, rootIndex + 1, inEnd);
        return root;
    }
}

其中，buildTree()方法接受先序遍历和中序遍历的数组作为参数，并返回构建好的二叉树的根节点。buildTreeHelper()方法是递归构建二叉树的辅助函数，它接受先序遍历和中序遍历的数组，以及当前子树的范围作为参数，并返回构建好的子树的根节点。在buildTreeHelper()方法中，首先判断递归终止条件，即先序遍历数组或中序遍历数组为空。然后，找到先序遍历数组的第一个节点作为根节点，并在中序遍历数组中找到根节点的位置。接着，递归构建左右子树，并将它们分别作为当前节点的左右子节点。最后，返回当前节点。

Java输入先序遍历给二叉树

可以通过递归的方式构建二叉树，具体步骤如下：

1. 根据先序遍历的顺序，获取当前节点的值作为根节点的值。
2. 读取下一个输入值，如果该值小于根节点的值，则该值为左子树的根节点；否则为右子树的根节点。
3. 递归调用步骤 1 和步骤 2，构建左子树和右子树。

下面是 Java 实现代码：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private int index = 0;
    
    public TreeNode buildTree(int[] preorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        return buildTreeHelper(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    
    private TreeNode buildTreeHelper(int[] preorder, int lower, int upper) {
        if (index >= preorder.length) {
            return null;
        }
        int val = preorder[index];
        if (val < lower || val > upper) {
            return null;
        }
        index++;
        TreeNode root = new TreeNode(val);
        root.left = buildTreeHelper(preorder, lower, val);
        root.right = buildTreeHelper(preorder, val, upper);
        return root;
    }
}

其中，index 表示当前遍历到的先序遍历数组的下标，lower 和 upper 表示当前节点的取值范围。在递归调用时，左子树的取值范围为 [lower, val)，右子树的取值范围为 (val, upper]。