二叉树的前序中序后序遍历-zhyjc6's Blog

二叉树的遍历分为深度优先遍历(DFS)和广度优先遍历(BFS)，其中深度优先遍历又分为前序遍历、中序遍历和后序遍历。广度优先遍历即层次遍历，只有遍历完当前层中的所有结点后才继续遍历下一层的结点。

前序遍历：根结点 —> 左子树 —> 右子树。先访问该节点，然后访问该节点的左子树和右子树；
中序遍历：左子树—> 根结点 —> 右子树。先访问该节点的左子树，然后访问该节点，再访问该节点的右子树；
后序遍历：左子树 —> 右子树 —> 根结点。想访问该节点的左子树和右子树，然后访问该节点。
层次遍历：只需按层次从上到下遍历即可

深度优先遍历通常是使用递归实现，使用迭代加栈也可以达到相同的效果。但是这两种方式的时间复杂度和空间复杂度都是$O(n)$，而莫里斯遍历的空间复杂度可以达到$O(1)$，时间复杂度也同样为$O(n)$。也就是说莫里斯遍历不需要额外空间就可以达到和普通遍历一样的时间复杂度。原因是其使用叶结点的右指针指向其祖宗根结点，从而可以在遍历完左子树后能跳回原来的根结点，然后继续遍历右子树。

莫里斯遍历模板

void preOrderMorris(TreeNode* root) {
	if (!root) {
		return;
	}
	TreeNode* cur1 = root;//当前开始遍历的节点
	TreeNode* cur2 = NULL;//记录当前结点的左子树
	while (cur1) {
		cur2 = cur1 -> left;
		if (cur2) {//存在左子树
			while (cur2->right && cur2->right != cur1) {//找到当前左子树的最右侧节点
				cur2 = cur2->right;
			}
			if (!cur2->right) {//如果根结点没有连接其左子树的最右结点，创建连接然后往左走一步
				cur2->right = cur1;
				cur1 = cur1->left;
				continue;
			} else {//根结点已经连接了其左子树的最右结点，说明左子树已经处理完，现在回到了根结点，把连接断开，还原树的结构
				cur2->right = NULL;
			}
		} 
		cur1 = cur1->right;//左子树处理完，向右走一步
	}
}

前序遍历

代码验证请到：https://leetcode.com/problems/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) {}
 * };
 */

递归

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ret;
    preDFS(root, ret);
    return ret;
}
void preDFS(TreeNode* root, vector<int> &v) {
    if (root) {
        v.push_back(root->val);
        preDFS(root->left, v);
        preDFS(root->right, v);
    }
}

迭代

迭代一：栈辅助1

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ret;
    stack<TreeNode*> stk;
    if (!root) return {};
    stk.push(root);
    while (!stk.empty()) {
        TreeNode* cur = stk.top();
        stk.pop();
        ret.push_back(cur->val);
        if (cur->right) {
            stk.push(cur->right);
        }
        if (cur->left) {
            stk.push(cur->left);
        }
    }
    return ret;
}

迭代二：栈辅助2

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> stack;
    TreeNode *cur = root;
    while (cur || !stack.empty()) {
        if (cur) {
            res.push_back(cur->val);
            stack.push(cur);
            cur = cur->left;
        } else {
            cur = stack.top(); stack.pop();
            cur = cur->right;
        }
    }
    return res;
}

迭代三：莫里斯遍历

在某个根结点创建连线的时候打印根结点。因为创建连接只有一次，后面就是进入其左子树了
没有左子树直接打印根结点

vector<int> preorderTraversal(TreeNode* root) {
    if (!root) return {};
    vector<int> ret;
    TreeNode* cur1 = root;//当前开始遍历的节点
    TreeNode* cur2 = NULL;//记录当前结点的左子树
    while (cur1) {
        cur2 = cur1->left;
        if (cur2) {//有左子树
            while (cur2->right && cur2->right != cur1) {
                cur2 = cur2->right;
            }
            if (!cur2->right) {//当前结点没有连接其左子树的最右结点
                ret.push_back(cur1->val);
                cur2->right = cur1;
                cur1 = cur1->left;
                continue;
            } else {//已经连接，说明左子树遍历完成，断开连接
                cur2->right = NULL;
            }
        } else {//没有左子树
            ret.push_back(cur1->val);
        }
        cur1 = cur1->right;//左子树处理完，向右走一步
    }
    return ret;
}

中序遍历

代码验证请到：https://leetcode.com/problems/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) {}
 * };
 */

递归

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        preDFS(root, ret);
        return ret;
    }
    void preDFS(TreeNode* root, vector<int> &v) {
        if (root) {
            preDFS(root->left, v);
            v.push_back(root->val);
            preDFS(root->right, v);
        }
    }

迭代

迭代一：栈辅助1

一直向左走，一路上不断入栈，走到尽头。然后从栈顶取出结点，此时是该子树的最左结点，加入结果集。然后进入右子树，继续执行以上操作直到栈为空。

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stack;
        TreeNode *cur = root;
        while (cur || !stack.empty()) {
            while (cur) {
                stack.push(cur);
                cur = cur->left;
            }
            cur = stack.top();
            stack.pop();
            res.push_back(cur->val);
            cur = cur->right;
        }
        return res;
    }

迭代二：栈辅助2

同样是以上思路，不过是完全不同的代码实现。

vector<int> inorderTraversal(TreeNode* root) {
    if (!root) return {};
    stack<TreeNode*> stack;
    vector<int> res;
    TreeNode *cur = root;
    while (cur || !stack.empty()) {
        if (cur) { //当前结点不为空，入栈，进入其左子树
            stack.push(cur);
            cur = cur->left;
        } else { //当前结点为空，取栈顶元素，弹出栈顶，进入右子树
            cur = stack.top(); stack.pop();
            res.push_back(cur->val); //遇到NULL了再回退到上一结点，并加入结果集
            cur = cur->right;
        }
    }
    return res;
}

迭代三：莫里斯遍历

不管左子树为不为空，先操作左子树，然后打印当前根结点，即在进入右子树前打印根结点。

vector<int> inorderTraversal(TreeNode* root) {
    if (!root) return {};
    vector<int> ret;
    TreeNode* cur1 = root;//当前开始遍历的节点
    TreeNode* cur2 = NULL;//记录当前结点的左子树
    while (cur1) {
        cur2 = cur1->left;
        if (cur2) {
            while (cur2->right && cur2->right != cur1) {
                cur2 = cur2->right;
            }
            if (!cur2->right) {//当前结点没有连接其左子树的最右结点
                cur2->right = cur1;
                cur1 = cur1->left;
                continue;
            } else {//已经连接，说明左子树遍历完成，断开连接
                cur2->right = NULL;
            }
        }
        ret.push_back(cur1->val);//上面左子树操作完成，打印根结点
        cur1 = cur1->right;//左子树处理完，向右走一步
    }
    return ret;
}

后序遍历

代码验证请到：https://leetcode.com/problems/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) {}
 * };
 */

递归

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;
        postDFS(root, ret);
        return ret;
    }
    void postDFS(TreeNode* root, vector<int> &v) {
        if (root) {
            postDFS(root->left, v);
            postDFS(root->right, v);
            v.push_back(root->val);
        }
    }

迭代

迭代一：栈辅助1

使用前序遍历的转换

前序遍历是root->left->right，中序遍历是left->root->right，后序遍历是left->right->root。前序遍历交换两行代码顺序就可以很容易地变成root->right->left，将其得到的结果逆序输出就得到后序遍历了。

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> ret;
    stack<TreeNode*> stk;
    if (!root) return ret;
    stk.push(root);
    while (!stk.empty()) {
        TreeNode* temp = stk.top();
        stk.pop();
        ret.push_back(temp->val);
        if (temp->left) stk.push(temp->left);
        if (temp->right) stk.push(temp->right);
    }
    reverse(ret.begin(), ret.end());
    return ret;
}

迭代二：栈辅助2

同样是以上思路，但是是不同的代码实现。

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> stack;
    TreeNode *cur = root;
    while (cur || !stack.empty()) {
        if (cur) {
            res.push_back(cur->val);
            stack.push(cur);
            cur = cur->right;
        } else {
            cur = stack.top(); stack.pop();
            cur = cur->left;
        }
    }
    reverse(res.begin(), res.end());
    return res;
}

迭代三：栈辅助3

将当前左子树的全部左结点依次入栈，再依次处理它们的右结点。关键部分是定义了一个指针变量pre用来存储上一个输出的结点，这样当从当前根结点的右子树中回溯到根结点时，由于根结点有右结点，因此会出现死循环，而定义的指针变量pre就可以识别其是从右子树回来的，因此不会向右走了。

指针变量pre和NULL共同构成了遍历的边界。

vector<int> postorderTraversal(TreeNode* root) {
    stack<TreeNode*> stk;
    vector<int> ret;
    TreeNode *pre = NULL, *cur = root;
    while (cur || !stk.empty()) {
        while (cur) {//左结点全部入栈，仅需处理右结点
            stk.push(cur);
            cur = cur->left;
        }
        cur = stk.top();
        //如果当前结点的右结点为空或已经访问过
        if (!cur->right || cur->right == pre) {
            ret.push_back(cur->val);
            stk.pop();
            pre = cur;
            cur = NULL;
        } else {
            cur = cur->right;
        }
    }
    return ret;
}

迭代四：由前序遍历转换的莫里斯遍历

和栈实现的迭代类似，莫里斯的后序遍历也可以通过将先序遍历root->left->right改成root->right->left，然后再将结果逆序输出得到正确结果。只需要将莫里斯前序遍历中的所有左改为右，右改为左，然后输出之前将结果逆序即可。

vector<int> postorderTraversal(TreeNode* root) {
    if (!root) return {};
    vector<int> ret;
    TreeNode* cur1 = root;//当前开始遍历的节点
    TreeNode* cur2 = NULL;//记录当前结点的右子树
    while (cur1) {
        cur2 = cur1->right;
        if (cur2) {//有右子树
            while (cur2->left && cur2->left != cur1) {
                cur2 = cur2->left;
            }
            if (!cur2->left) {//当前结点没有连接其右子树的最左结点
                ret.push_back(cur1->val);
                cur2->left = cur1;
                cur1 = cur1->right;
                continue;
            } else {//已经连接，说明右子树遍历完成，断开连接
                cur2->left = NULL;
            }
        } else {//没有右子树
            ret.push_back(cur1->val);
        }
        cur1 = cur1->left;//左子树处理完，向右走一步
    }
    reverse(ret.begin(), ret.end());
    return ret;
}

层次遍历

下面的遍历都是将每一层的结点单独放在一个数组里，如果将结点全部放在一个数组里，实现起来会更简单。

代码验证请到：https://leetcode.com/problems/binary-tree-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) {}
 * };
 */

递归

void helper(TreeNode* root, int level, vector<vector<int>> &ret) {
    if (!root) return;
    if (ret.size() <= level) {//vector数少于层数
        ret.push_back(vector<int>());
    }
    ret[level].push_back(root->val);
    helper(root->left, level + 1, ret);
    helper(root->right, level + 1, ret);
}
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> ret;
    helper(root, 0, ret);
    return ret;
}

迭代

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