二叉树与N叉树遍历

二叉树遍历的主要类型有：

• Preorder Traversal (144), Inorder Traversal (94), Postorder Traversal (145)
• Zig-Zag Traversal (103)（《算法导论》里将“遍历”用walk来描述）;
• Vertical Order Traversal (987) ;
• Level Order Traversal (102 & 107)

如果扩展一下，考虑N叉树，主要类型可以扩充为：

• N-ary Tree Preorder Traversal (589), N-ary Tree Postorder Traversal (590),
• N-ary Tree Level Order Traversal (429)

二叉树的遍历方法主要有三种：

• 递归
• 非递归，使用辅助栈
• Morris线索二叉树

这里主要总结一下**线索二叉树**和后序遍历里面使用栈的解法。

二叉树的前序、中序和后序遍历

使用辅助栈的前序遍历

• LeetCode 144.Binary Tree Preorder Traversal

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if (!root) return res;

        stack<TreeNode *> store;
        store.push(root);

        while (!store.empty()) {
            TreeNode *p = store.top();
            store.pop();
            res.push_back(p -> val);
            if (p -> right) store.push(p -> right);
            if (p -> left) store.push(p -> left);
        }

        return res;
    }
};

使用辅助栈的中序遍历

• LeetCode 94.Binary Tree Inorder Traversal

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if (!root) return res;

        stack<TreeNode *> s;
        TreeNode *p = root;

        while (!s.empty() || p != nullptr) {
            if (p != nullptr) {
                s.push(p);
                p = p -> left;
            }
            else {
                p = s.top();
                s.pop();
                res.push_back(p -> val);
                p = p -> right;
            }
        }

        return res;
    }
};

使用辅助栈的后序遍历

• LeetCode 145. Binary Tree Postorder Traversal

使用栈的解法主要有两种：一种是使用双栈，一种是使用单栈。

先看使用单栈的方法，考虑前序遍历：根 - 左 - 右，如果交换遍历左、右的顺序，那么就变成根 - 右 - 左，最后按照访问的顺序倒序输出。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if (!root) return res;

        stack<TreeNode *> s;
        s.push(root);

        while (!s.empty()) {
            TreeNode *p = s.top();
            s.pop();
            res.push_back(p -> val);
            if (p -> left) s.push(p -> left);
            if (p -> right) s.push(p -> right);
        }
        reverse(res.begin(), res.end());

        return res;
    }
};

双栈的解法的解法和单栈解法相比，仍然是改进前序遍历中遍历左右子树的顺序，只不过这里我们采用增加一个辅助栈的方式来存储遍历的顺序，然后依次输出到vector里，空间复杂度仍然是O(n)，只不过是常数项变大。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if (!root) return res;

        stack<TreeNode *> s, tmp;
        s.push(root);

        while (!s.empty()) {
            TreeNode *p = s.top();
            s.pop();
            tmp.push(p);
            if (p -> left) s.push(p -> left);
            if (p -> right) s.push(p -> right);
        }
        while (!tmp.empty()) {
            TreeNode *p = tmp.top();
            tmp.pop();
            res.push_back(p -> val);
        }

        return res;
    }
};

线索二叉树的前序和中序遍历

网上对于线索二叉树的讲解大部分是给出构造方法，但是中间的具体思考细节却鲜有描述。线索二叉树的原始论文 Traversing binary trees simply and cheaply 现在已经无法看到了。严蔚敏的《数据结构(C语言版)》虽然其实现方法需要去增加节点存储的数据，但也为我们提供了一种思路。《数据结构：题解与扩展》（是数据结构课程教材《数据结构：思想与实现》的配套书籍）在5.4节给出了中序遍历的线索二叉树构造方法，但是程序实现并不太适合作为写算法的参考。在这些材料的基础上，我们给出一种比较简洁易懂的写法。

这里采用严蔚敏书籍里对于线索的定义，但是程序实现并不参考。对于二叉树里父节点、子节点的定义无需赘述，遍历的本质是将一个非线性结构进行线性化的操作：将二叉链表转化成一个数组，在连续的空间内存储。对于当前节点，上一个遍历的节点称为**前驱**，下一个遍历节点称为**后继**。这里我们将指向后继的指针称为**线索**（书中是将指向前驱的指针也称为线索），这样就免于去为每个节点增加额外的数据。

书中给出了一个比较重要的结论：$n$个节点的二叉树必然存在$n+1$个空指针。这个结论的证明比较简单，每个节点都有2个指针，所以$n$个节点共有$2n$个指针，节点是两两相连，那么共有$n-1$个指针非空，那么余下的$n+1$个指针必然是空指针，所以我们才有足够的空指针来建立线索。这样余下的$n+1$个空指针就被用去了$n-1$个来建立线索，那么剩下的两个空指针其实恰好被用来作为确定遍历的起点和终点。

这里采取**中序遍历**作为例子来分析。中序遍历顺序是：左子树 - 当前节点 - 右子树。所以遍历时当前节点的后继应该是右子树的最左子节点，同样其前驱应该是左子树的最右子节点。

第一步是建立线索：对于每一个当前节点，去寻找其左子树的最右子节点（前驱），然后让其右指针指向当前节点，完成线索的建立。

第二步是找到遍历的起始位置：中序遍历的起始点一定是根节点的左子树的最左子节点，根据建立线索的方式我们知道其左指针必定为空，所以才会作为遍历的判断条件。那么就应该读取当前节点存储的数据，根据前序遍历的顺序，当前节点应该转到其右子节点。第一步中存在的特殊情形（无左子树）也就包括在这里了。

第三步是要恢复二叉树：如果一个节点其左子树最右子节点的右指针指向当前节点，那么当前节点左子树的所有节点必然被全部访问过。因为我们开始遍历时访问到当前节点，必然是从其前驱过来的，其前驱是左子树最后一个被访问的节点，所以左子树都被访问过。那么按照顺序，当前节点被访问。进而访问其右子树。

于是访问右子树的子问题又变成了和上面三步一样的形式，于是程序就比较容易给出：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if (!root) return res;

        TreeNode * cur = root, *pre = nullptr;

        while (cur != nullptr) {
            //判断遍历子结构的起点
            if (cur -> left == nullptr) {
                res.push_back(cur -> val);
                cur  = cur -> right;
            }
            else {
                pre = cur -> left;
                //寻找当前节点的左子树的最右子节点
                while (pre -> right != nullptr && pre -> right != cur)
                    pre = pre -> right;

                //建立线索
                if (pre -> right == nullptr) {
                    pre -> right = cur;
                    cur = cur -> left;
                }
                //恢复二叉树原状
                else {
                    res.push_back(cur -> val);
                    pre -> right = nullptr;
                    cur = cur -> right;
                }
            }
        }

        return res;
    }
};

前序遍历的解法可以在 这里 实现。虽然它的实现和中序遍历很接近，只是输出的位置变了，但是程序的含义却有很大区别。

我们判断当前节点左指针是否为空，中序遍历的目的是为了寻找遍历的起点（同时涵盖了无左子树的特殊情况），但是前序遍历的判断只是为了处理特殊情形，即左子树为空的情况。

前序遍历建立线索的过程就需要输出当前节点，因为我们仍然采取和中序遍历一样的线索建立方法，那么当需要去建立索引时，也就意味着如果现在是中序遍历，那么需要建立线索的节点（当前节点的左子树的最右子节点）是当前节点的前驱，而在前序遍历里恰好当前节点转换成遍历的起始节点，所以在建立线索时输出。

**共同点**是中序遍历破坏线索恢复原状时，当前节点的左子树都被访问过了。

线索二叉树的后序遍历

对于后续遍历的分析，我们先写出上图的后续遍历结果：6-7-4-8-9-5-2-3-1。我们可以发现一个规律：假设我们站在某一个节点观察（视为当前节点），则后序遍历时其左节点到左子树的最右子节点的遍历顺序必然是**逆序且连续的**。比如我们以1作为当前节点，按照刚才的结论，其左节点到左子树的最右子节点是2-5-9，访问顺序是9-5-2，逆序且连续。这个结论很容易证明，只需要把此图的2的左子树抽象表示，2的右子树的每个子节点的左子树也抽象表示，那么根据访问顺序，遍历时必然是先遍历完2的左子树，然后遍历2的右子树肯定在遍历右节点时左边的抽象部分要访问完成，所以遍历顺序是连续的。

蓝色的线就是逆序访问时的顺序。它的实现程序和另外两种的区别在于，仅有一个输出环节，因为无左子树还需要去考虑右子树是否为空，当时还需要考虑一个特殊情况，只有根节点一个节点，那么完全按照前面建立线索的方法，则无法访问根节点，所以建立一个虚拟节点，让其左指针指向根节点则解决此特殊情况。

之所以需要逆序打印，仍然是考虑前序遍历：当前节点 - 左子树 - 右子树，所以当访问到当前节点的左子树的最右子节点，并且已经完成线索化时，说明我们找到了前序遍历中右子树的前驱，当前节点的左节点就是前序遍历左子树的起始节点，根据上面的分析，两个节点之间的逆序路径就是逆序遍历的顺序。

逆序遍历其实就是简单的单链表反转的变形问题。

class Solution {
public:
    void reverse(TreeNode *from, TreeNode *to) {
        if (from == to)
            return;

        TreeNode *pre = from, *cur = from -> right, *tmp;
        while (true) {
            tmp = cur -> right;
            cur -> right = pre;
            pre = cur;
            cur = tmp;
            if (pre == to)
                break;
        }
    }

    void printReverse(TreeNode* from, TreeNode *to, vector<int> & res) {
        reverse(from, to);

        TreeNode *p = to;
        while (true) {
            res.push_back(p -> val);
            if (p == from)
                break;
            p = p -> right;
        }

        reverse(to, from);
    }

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if (!root) return res;

        TreeNode dummy(0);
        dummy.left = root;
        TreeNode *cur = &dummy, *prev = nullptr;

        while (cur) {
            if (cur -> left == nullptr) {
                cur = cur -> right;
            }
            else {
                prev = cur -> left;
                while (prev -> right != nullptr && prev -> right != cur)
                    prev = prev -> right;

                if (prev -> right == nullptr) {
                    prev -> right = cur;
                    cur = cur -> left;
                }
                else {
                    printReverse(cur -> left, prev, res);  // call print
                    prev -> right = nullptr;
                    cur = cur -> right;
                }
            }
        }

        return res;
    }
};

二叉树的层序遍历

• LeetCode 102.二叉树的层序遍历
• LeertCode 107.二叉树的层次遍历 II

//LeetCode 102.二叉树的层序遍历
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        vector<vector<int>> res;
        if (!root) return res;
        queue<TreeNode *> q;
        q.push(root);

        while (!q.empty()) {
            int n = q.size();
            vector<int> level;
            for (int i = 0; i < n; ++i) {
                TreeNode *tmp = q.front(); q.pop();
                level.push_back(tmp -> val);
                if (tmp -> left) q.push(tmp -> left);
                if (tmp -> right) q.push(tmp -> right);
            }
            res.push_back(level);
        }

        return res;
    }
};

层序遍历的关键点有两个，一个是利用辅助队列，另一个就是记录队列里元素的数量，采用一个for循环去取出每一层节点的值。

二叉树的之字形遍历

• LeetCode 103.Binary Tree Zigzag Level Order Traversal

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) return res;

        queue<TreeNode *> q;
        q.push(root);
        int floor = 0;
        while (!q.empty()) {
            int len = q.size();
            vector<int> level(len);
            for (int i = q.size(); i > 0; --i) {
                TreeNode * p = q.front();
                q.pop();
                if (floor & 1) level[i - 1] = p -> val;
                else level[len - i] = p -> val;
                if (p -> left) q.push(p -> left);
                if (p -> right) q.push(p -> right);
            }
            res.push_back(level);
            ++floor;
        }

        return res;
    }
};

每次遍历每一层时，存储每层元素的数组的大小是确定的，就是q.size()，所以可以直接确定每层元素在对应数组的位置。

二叉树的垂向遍历

• LeetCode 987.Vertical Order Traversal of a Binary Tree

第一种解法：

map里面嵌套map：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    map<int, map<int, vector<int>>> mp;

    void traverse(TreeNode* root, int pos, int level)
    {
        mp[pos][level].push_back(root -> val);
        if (root -> left) traverse(root -> left, pos - 1, level + 1);
        if (root -> right) traverse(root -> right, pos + 1, level + 1);
    }

    vector<vector<int>> verticalTraversal(TreeNode* root) {  
        vector<vector<int>> res;
        if(!root) return res;

        traverse(root, 0, 0);
        for(auto it : mp)
        {
            vector<int> cur;
            for(auto it2 : it.second)
            {
                vector<int> &tmp = it2.second;
                sort(tmp.begin(), tmp.end());
                for(int i = 0; i < tmp.size(); ++i)
                    cur.push_back(tmp[i]);
            }
            res.push_back(cur);
        }
        return res;
    }
};

思路是利用节点的位置pos作为键，由层数和节点组成的map作为值，所以遍历存在两层循环，第一层是把所有处于同一列的节点放置于同一数组内，第二层是对同一个数组内的元素根据层数由上层到下层来排序。

第二种方法：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    map<pair<int, int>, vector<int>> mp;

    void traverse(TreeNode* root, int pos, int level)
    {
        mp[make_pair(pos, level)].push_back(root -> val);
        if (root -> left) traverse(root -> left, pos - 1, level + 1);
        if (root -> right) traverse(root -> right, pos + 1, level + 1);
    }

    vector<vector<int>> verticalTraversal(TreeNode* root) {  
        vector<vector<int>> res;
        if(!root) return res;

        traverse(root, 0, 0);
        int lastPos = INT_MIN;
        for(auto pr : mp)
        {
            int pos = pr.first.first; //节点所在的列
            vector<int> tmp(pr.second);
            sort(tmp.begin(), tmp.end());
            if (pos != lastPos) {
                res.push_back(tmp);
            }
            else {
                for (auto e : tmp) res[res.size() - 1].push_back(e);
            }
            lastPos = pos;
        }

        return res;
    }
};

这种方法是把坐标pos, level作为键，每个坐标对应的节点作为值，因为map已经对坐标进行了排序，所以考虑的是当pos也就是列相同但层数不同的情况。所以用一个变量lastPos来记录上一次循环的pos值，如果相同，那么说明当前的vector和上一次的属于同一列，那么就把当前数组的元素加入到最终数组最后一个数组里面。如果pos != lastPos，说明它们属于不同的列，所以最终数组新增一个数组（注意，前面的情况没有新增数组）.

遍历二叉树的所有路径

一条二叉树的路径定义为从根节点到叶节点上经过的节点组成的序列。

• LeetCode 1457.Pseudo-Palindromic Paths in a Binary Tree
• LintCode 480. 二叉树的所有路径

样例

样例 1:

输入：{1,2,3,#,5}
输出：["1->2->5","1->3"]
解释：
   1
 /   \
2     3
 \
  5

样例 2:

输入：{1,2}
输出：["1->2"]
解释：
   1
 /   
2     

//LintCode 480. 二叉树的所有路径
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
    vector<string> res;
public:
    /**
     * @param root: the root of the binary tree
     * @return: all root-to-leaf paths
     */
    vector<string> binaryTreePaths(TreeNode * root) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (!root) return res;

        string tmp;
        traversal(root, tmp);
        return res;
    }

    void traversal(TreeNode *root, string tmp)
    {
        tmp += to_string(root -> val);
        if (root -> left) traversal(root -> left, tmp + "->");
        if (root -> right) traversal(root -> right, tmp + "->");
        if (!root -> left && !root -> right) res.push_back(tmp);
    }
};

N叉树的前序、中序和后序遍历

• LeetCode 589.N叉树的前序遍历

N叉树前序遍历递归解法：

//LeetCode 589.N叉树的前序遍历
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> res;
        if (!root) return res;

        preorder(root, res);

        return res;
    }

    void preorder(Node *root, vector<int> & res) {
        res.push_back(root -> val);
        for (auto e : root -> children) {
            if (e) preorder(e, res);
        }
    }
};

N叉树前序遍历非递归的写法，和二叉树基本一样，小小的区别就是之前二叉树入栈是先右再左，这里其实就是逆序遍历数组。

//LeetCode 589.N叉树的前序遍历
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> res;
        if (!root) return res;

        stack<Node *> s;
        s.push(root);
        while (!s.empty()) {
            Node * p = s.top();
            s.pop();
            res.push_back(p -> val);
            for (int i = (p -> children).size() - 1; i >= 0; --i) {
                if ((p -> children)[i]) s.push((p -> children)[i]);
            }
        }

        return res;
    }
};

- [x] LeetCode 590.N叉树的后序遍历

N叉树后序遍历递归解法：

//LeetCode 590.N叉树的后序遍历
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    vector<int> postorder(Node* root) {
        vector<int> res;
        if (!root) return res;

        postorder(root, res);

        return res;
    }

    void postorder(Node * root, vector<int> & res) {
        for (auto e : root -> children) {
            if (e) postorder(e, res);
        }
        res.push_back(root -> val);
    }
};

N叉树后序遍历使用辅助栈的非递归解法：

//LeetCode 590.N叉树的后序遍历
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    vector<int> postorder(Node* root) {
        vector<int> res;
        if (!root) return res;

        stack<Node *> s;
        s.push(root);
        while (!s.empty()) {
            Node *p = s.top();
            s.pop();
            res.push_back(p -> val);
            for (auto e : p -> children) {
                if (e) s.push(e);
            }
        }
        reverse(res.begin(), res.end());

        return res;
    }
};

因为后序遍历的顺序是“左-右-根”，可以借助辅助栈来实现“根-右-左”的遍历，最终结果只需要翻转即可，比较耗时间的步骤是数组翻转的步骤。

N叉树的层序遍历

• LeetCode 429.N叉树的层序遍历（使用辅助队列）

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        vector<vector<int>> res;
        if (!root) return res;

        queue<Node *> q;
        q.push(root);
        while (!q.empty()) {
            int n = q.size();
            vector<int> tmp;
            for (int i = 0; i < n; ++i) {
                Node *p = q.front(); q.pop();
                tmp.push_back(p -> val);
                auto & v = p -> children;
                for (auto e : v) q.push(e);
            }
            res.push_back(tmp);
        }

        return res;
    }
};

典型题目

• LeetCode 1008.先序遍历构造二叉树（利用二叉搜索树的性质）
• LeetCode 429.N叉树的层序遍历（使用辅助队列）