> For the complete documentation index, see [llms.txt](https://mabuxi.gitbook.io/mabuxi/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mabuxi.gitbook.io/mabuxi/leetcode-summary/tree/traversal.md).

# Traversal

## Preorder Traversal

[*114 Flatten Binary Tree to Linked List*](https://leetcode.com/problems/flatten-binary-tree-to-linked-list/description/)

Revised preorder traversal

这道题，乍一看好像很简单，直接pre-order traversal (curr -> L -> R)，然后按顺序依次转化成rootNode的右子树。这样的话，我们需要另一个数组存储我们的pre-order traversal，再依次粘贴到rootNode的右子树上。

我们可以用递归，从右子树开始扫起，进行 reverse preorder，即 R -> L -> curr。同时keep 一个 global 的 prev pointer, pointing to the last executed node. 每次我们需要对当前node进行，root.right = prev, root.left = null, prev = root

```java
public void flatten(TreeNode root) {
    helper(root, null);
}
private TreeNode helper(TreeNode root, TreeNode pre) {
    if (root == null) return pre;
    pre = helper(root.right, pre);
    pre = helper(root.left, pre);
    root.right = pre;
    root.left = null;
    return root;
}
```

## Inorder Traversal

[*94 Binary Tree Inorder Traversal*](https://leetcode.com/problems/binary-tree-inorder-traversal/description/)

Iterative 方法 in order 遍历二叉树。借助 Stack 实现。

```java
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new LinkedList<>();
    TreeNode cur = root;
    while(cur != null || !stack.isEmpty() ) {
        if (cur != null) {
            stack.offerLast(cur);
            cur = cur.left;
        } else {
            cur = stack.pollLast();
            res.add(cur.val);
            cur = cur.right;
        }
    }
    return res;
}
```

## Postorder Traversal

[*145 Binary Tree Postorder Traversal*](https://leetcode.com/problems/binary-tree-postorder-traversal/description/)

循环的方式后序遍历二叉树。记忆点：1.从上往下和从下往上的过程不太一样，需要分开讨论。2.从上往下的时候，需要先遍历左子树，再右子树，最后是节点。3.从下往上的时候，也有两种情况，第一种是从右子树上来或者左子树上来并且已无右子树可以遍历，第二种是从左子树上来并且还有右子树可以遍历。

{% tabs %}
{% tab title="Recursion Solution" %}

{% endtab %}

{% tab title="Iterative Solution" %}

```java
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Deque<TreeNode> stack = new LinkedList<>();
    stack.add(root);
    TreeNode pre = null;
    while (!stack.isEmpty()) {
        TreeNode cur = stack.peekFirst();
        // if we are going down, try to go left first
        if (pre == null || pre.left == cur || pre.right == cur) {
            if (cur.left != null) {
                stack.offerFirst(cur.left);
            } else if (cur.right != null) {
                stack.offerFirst(cur.right);
            } else {
                stack.pollFirst();
                res.add(cur.val);
            }
        } 
        // if we are going up from the right side or from left side but we can not go right afterwards
        else if (cur.right == pre || cur.left == pre && cur.right == null) {
            stack.pollFirst();
            res.add(cur.val);
        }
        // if we are going up from the left side and we can go down right side
        else {
            stack.offerFirst(cur.right);
        }
        pre = cur;
    }
    return res;
}
```

{% endtab %}
{% endtabs %}


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mabuxi.gitbook.io/mabuxi/leetcode-summary/tree/traversal.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.