二叉树翻转(递归+非递归)
文章目录
前言
二叉树翻转是一道经典的面试编程题，经常出现在各大公司的招聘笔试面试环节。
这里还有个趣事，Homebrew 的作者 Max Howell 某天去 Google 面试，面试官出了一道反转二叉树的题目，然而 Max Howell 没答上来，结果被拒。面试官的评语是：“我们 90％ 的工程师使用您编写的软件，但是您却无法在面试时在白板上写出翻转二叉树这道题，所以滚蛋吧”。
可见，在求职面试过程中，即使你是一位优秀的程序员，如果答不上算法题，那么在算法方面的能力将被面试官认为是不及格的，甚至无法被聘用。
问题描述
给定一个二叉树，输出其镜像。
Input:
4
/ \
2 7
/ \ / \
1 3 6 9Output:
4
/ \
7 2
/ \ / \
9 6 3 1递归实现
- 问题分析
翻转一个二叉树，直观上看，就是把二叉树的每一层左右顺序倒过来。比如问题中的例子，第三层 1-3-6-9 经过变换后变成了9-6-3-1，顺序反过来就对了。
再仔细观察一下，对于上面的例子，根结点的左子结点及其所有的子孙结点构成根节点的左子树，同样的，根结点的右子结点及其所有的子孙节点构成根结点的右子树。因此翻转一个二叉树，就是把根结点的左子树翻转一下，同样的把右子树翻转一下，在交换左右子树就可以了。
当然，翻转左子树和右子树的过程和当前翻转二叉树的过程没有区别，就是递归的调用当前的函数就可以了。
因此，翻转二叉树的步骤可总结如下： （1）交换根结点的左子结点与右子结点； （2）翻转根结点的左子树（递归调用当前函数）； （3）翻转根结点的右子树（递归调用当前函数）。
- 具体实现
// 二叉树结点结构体
struct BinaryTreeNode
{
int m_key;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
BinaryTreeNode() {
m_key = 0;
m_pLeft = m_pRight = nullptr;
}
};
// @brief: 翻转二叉树
// @param: root 二叉树根结点
// @ret: 翻转后的二叉树根结点
BinaryTreeNode* invertBT(BinaryTreeNode* root) {
if (root == nullptr) return root;
// 交换左右孩子结点
auto tmp = root->m_pLeft;
root->m_pLeft = root->m_pRight;
root->m_pRight = tmp;
// 递归处理左右子树
invertBT(root->m_pLeft);
invertBT(root->m_pRight);
return root;
}- 验证实现
验证代码涉及二叉树的创建和遍历，验证如下：
// @brief: 前序递归遍历
void preorderRecursion(BinaryTreeNode* root) {
if (root == nullptr) return;
cout << " " << root->m_key;
preorderRecursion(root->m_pLeft);
preorderRecursion(root->m_pRight);
}
// @brief: 根据前序序列和中序序列构建二叉树
// @param: preOrder:前序序列; midOrder:中序序列; len:结点数
// @ret: 二叉树根结点
BinaryTreeNode* constructPreMid(int* preOrder, int* midOrder, int len) {
if (preOrder == nullptr || midOrder == nullptr || len <= 0) return nullptr;
// 前序遍历的第一个值就是根节点
int rootKey = preOrder[0];
BinaryTreeNode* root = new BinaryTreeNode;
root->m_key = rootKey;
// 只有一个结点
if (len == 1 && *preOrder == *midOrder) return root;
// 在中序序列中找到根结点
int* rootMidOrder = midOrder;
// 左子树结点数
int leftLen = 0;
while (*rootMidOrder != rootKey && rootMidOrder <= (midOrder + len - 1)) {
++rootMidOrder;
++leftLen;
}
// 在中序序列未找到根结点，输入错误
if (*rootMidOrder != rootKey) return nullptr;
// 构建左子树
if (leftLen>0) {
root->m_pLeft = constructPreMid(preOrder + 1, midOrder, leftLen);
}
// 构建右子树
if (len - leftLen - 1>0) {
root->m_pRight = constructPreMid(preOrder + leftLen + 1, rootMidOrder + 1, len - leftLen - 1);
}
return root;
}
int main() {
// 前序+中序构建二叉树
int preorder[] = {4,2,1,3,7,6,9};
int midorder[] = {1,2,3,4,6,7,9};
auto root = constructPreMid(preorder, midorder, 7);
preorderRecursion(root);
cout << endl;
// 翻转二叉树
auto invertRoot = invertBT(root);
cout << "--- after invert ---" << endl;
preorderRecursion(invertRoot); // 4,7,9,6,2,3,1
}运行输出：
4 2 1 3 7 6 9
--- after invert ---
4 7 9 6 2 3 1非递归实现
- 问题分析
二叉树反转，实际上是遍历二叉树的每一个结点，对其左右结点进行交换。那么我们可以采用层序遍历，使用队列来存放待遍历的结点。
具体步骤如下： （1）首先把二叉树的根结点送入队列； （2）访问队首结点，把它的左子结点和右子结点分别入队列，然后交换其左右子结点，最后队首结点出队列； （3）重复上面两步操作，直至队列空。
- 具体实现
// @brief: 非递归翻转二叉树
// @param: 二叉树根结点
// @ret: 翻转后的二叉树根结点
BinaryTreeNode* invertBTNonrecu(BinaryTreeNode* root) {
if (root == nullptr) return root;
queue<BinaryTreeNode*> queue;
queue.push(root);
while (!queue.empty()){
// 取队首结点
BinaryTreeNode* cur = queue.front();
// 左右子结点入队列
if (cur->m_pLeft != nullptr) queue.push(cur->m_pLeft);
if (cur->m_pRight != nullptr) queue.push(cur->m_pRight);
// 交换左右子结点
auto tmp = cur->m_pLeft;
cur->m_pLeft = cur->m_pRight;
cur->m_pRight = tmp;
// 队首结点出队列
queue.pop();
}
return root;
}- 验证实现
int main(){
// 前序+中序构建二叉树
int preorder[] = {4,2,1,3,7,6,9};
int midorder[] = {1,2,3,4,6,7,9};
BinaryTreeNode* root = constructPreMid(preorder, midorder, 7);
preorderRecursion(root);
cout << endl;
// 非递归翻转二叉树
cout << "--- after non-recursive invert ---" << endl;
auto invertRoot = invertBTNonrecu(root);
preorderRecursion(invertRoot); // 4,7,9,6,2,3,1
}运行输出：
4 2 1 3 7 6 9
--- after non-recursive invert ---
4 7 9 6 2 3 1