144. Duyệt cây nhị phân theo thứ tự trước (danh sách đệ quy)

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> resultList = new ArrayList<>();
    preOrder(root, resultList);
    return resultList;
}

// Hàm đệ quy nhận nút và danh sách kết quả
public void preOrder(TreeNode currentNode, List<Integer> resultList) {
    if (currentNode == null) {
        return;
    } else {
        resultList.add(currentNode.val);
        preOrder(currentNode.left, resultList);
        preOrder(currentNode.right, resultList);
    }
}

145. Duyệt cây nhị phân theo thứ tự sau (danh sách đệ quy)

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> resultList = new ArrayList<>();
    postOrder(root, resultList);
    return resultList;
}

public void postOrder(TreeNode currentNode, List<Integer> resultList) {
    if (currentNode == null) {
        return;
    } else {
        postOrder(currentNode.left, resultList);
        postOrder(currentNode.right, resultList);
        resultList.add(currentNode.val);
    }
}

94. Duyệt cây nhị phân theo thứ tự giữa (danh sách đệ quy)

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> resultList = new ArrayList<>();
    inOrder(root, resultList);
    return resultList;
}

public void inOrder(TreeNode currentNode, List<Integer> resultList) {
    if (currentNode == null) {
        return;
    } else {
        inOrder(currentNode.left, resultList);
        resultList.add(currentNode.val);
        inOrder(currentNode.right, resultList);
    }
}

144. Duyệt cây nhị phân theo thứ tự trước (danh sách stack)

List<Integer> resultList = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null) {
    return resultList;
}
while (root != null || !stack.isEmpty()) {
    while (root != null) {
        stack.push(root);
        resultList.add(root.val);
        root = root.left;
    }
    TreeNode topNode = stack.peek();
    stack.pop();
    root = topNode.right;
}
return resultList;

94. Duyệt cây nhị phân theo thứ tự giữa (danh sách stack)

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> resultList = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    if (root == null) {
        return resultList;
    }
    while (root != null || !stack.isEmpty()) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        TreeNode topNode = stack.peek();
        stack.pop();
        resultList.add(topNode.val);
        root = topNode.right;
    }
    return resultList;
}

145. Duyệt cây nhị phân theo thứ tự sau (danh sách stack)

// Danh sách lưu kết quả
List<Integer> resultList = new ArrayList<>();
// Biến lưu nút đã duyệt
TreeNode lastVisited = null;
Stack<TreeNode> stack = new Stack<>();

while (!stack.isEmpty() || root != null) {
    // Duyệt sang bên trái và đẩy vào stack
    while (root != null) {
        stack.push(root);
        root = root.left;
    }
    // Lấy nút trên đỉnh stack (không pop)
    root = stack.peek();
    // Kiểm tra xem đã duyệt hết các nút bên phải chưa
    if (root.right == null || root.right == lastVisited) {
        resultList.add(root.val);
        stack.pop();
        lastVisited = root;
        root = null;
    } else {
        root = root.right;
    }
}

return resultList;