二叉树的遍历

1 数据结构

1.1 C++

struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL)
    {
    }
};

1.2 Java

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

2 递归遍历

2.1 递归前序遍历

遍历顺序：中、左、右

2.1.1 C++

void show(TreeNode *root)
{
    if (!root)
        return;
    cout << root->val << " ";
    show(root->left);
    show(root->right);
}

2.1.2 Java

public static void show(TreeNode root) {
    if (root == null)
        return;
    System.out.print(root.val + " ");
    show(root.left);
    show(root.right);
}

2.2 递归中序遍历

遍历顺序：左、中、右

2.2.1 C++

void show(TreeNode *root)
{
    if (!root)
        return;
    show(root->left);
    cout << root->val << " ";
    show(root->right);
}

2.2.2 Java

public static void show(TreeNode root) {
    if (root == null)
        return;
    show(root.left);
    System.out.print(root.val + " ");
    show(root.right);
}

2.3 递归后序遍历

遍历顺序：左、右、中

2.3.1 C++

void show(TreeNode *root)
{
    if (!root)
        return;
    show(root->left);
    show(root->right);
    cout << root->val << " ";
}

2.3.2 Java

public static void show(TreeNode root) {
    if (root == null)
        return;
    show(root.left);
    show(root.right);
    System.out.print(root.val + " ");
}

3 非递归遍历

非递归遍历，使用栈来实现。

3.1 非递归前序遍历

遍历顺序：中、左、右

要注意压栈的顺序，后压入的会先遍历。

3.1.1 C++

void show(TreeNode *root)
{
    stack<TreeNode *> s;
    s.push(root);
    while (!s.empty())
    {
        TreeNode *p = s.top();
        s.pop();
        if (p)
        {
            cout << p->val << " ";
            s.push(p->right);
            s.push(p->left);
        }
    }
}

3.1.2 Java

public static void show(TreeNode root) {
    Stack<TreeNode> s = new Stack<>();
    s.push(root);
    while (!s.empty()) {
        TreeNode p = s.pop();
        if (p != null) {
            System.out.print(p.val + " ");
            s.push(p.right);
            s.push(p.left);
        }
    }
}

3.2 非递归中序遍历

遍历顺序：左、中、右

主要思想：先将p指向root，然后进行循环
1. 如果p不为空，将p压入栈中，执行p = p->left。
2. 如果p为空，从栈顶取出元素赋值给p，输出p对应的值，执行p = p->right。

算法的难点在于如何防止重复压栈。

3.2.1 C++

void show(TreeNode *root)
{
    stack<TreeNode *> s;
    TreeNode *p = root;
    while (p || !s.empty())
    {
        if (p)
        {
            s.push(p);
            p = p->left;
        }
        else
        {
            p = s.top();
            s.pop();
            cout << p->val << " ";
            p = p->right;
        }
    }
}

3.2.2 Java

public static void show(TreeNode root) {
    Stack<TreeNode> s = new Stack<>();
    TreeNode p = root;
    while (p != null || !s.empty()) {
        if (p != null) {
            s.push(p);
            p = p.left;
        } else {
            p = s.pop();
            System.out.print(p.val + " ");
            p = p.right;
        }
    }
}

3.3 非递归后序遍历

遍历顺序：左、右、中

主要思想：先进行中、右、左的遍历，类似前序遍历，然后将结果逆序输出即可。
https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

3.3.1 C++

vector<int> postorderTraversal(TreeNode *root)
{
    vector<int> v, ans;
    stack<TreeNode *> s;
    s.push(root);
    while (!s.empty())
    {
        TreeNode *p = s.top();
        s.pop();
        if (p)
        {
            v.push_back(p->val);
            s.push(p->left);
            s.push(p->right);
        }
    }
    ans = vector<int>(v.rbegin(), v.rend());
    return ans;
}

3.3.2 Java

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> ans = new ArrayList<>();
        Stack<TreeNode> s = new Stack<>();
        s.push(root);
        while (!s.empty()) {
            TreeNode p = s.pop();
            if (p != null) {
                ans.add(p.val);
                s.push(p.left);
                s.push(p.right);
            }
        }
        Collections.reverse(ans);// 逆序
        return ans;
    }
}

4 层次遍历

层次遍历是一层一层的遍历，每一层从左到右遍历。借助队列的先进先出的特性来实现。

4.1 C++

void show(TreeNode *root)
{
    queue<TreeNode *> q;
    q.push(root);
    while (!q.empty())
    {
        TreeNode *p = q.front();
        q.pop();
        if (p)
        {
            cout << p->val << " ";
            q.push(p->left);
            q.push(p->right);
        }
    }
}

4.2 Java

public static void show(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        TreeNode p = q.poll();
        if (p != null) {
            System.out.print(p.val + " ");
            q.add(p.left);
            q.add(p.right);
        }
    }
}