LeetCode 刷题 [C++] 第226题.翻转二叉树

题目描述

index.php/tags-41973.html" >���你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

题目分析

深度优先搜索（DFS）- 递归方式

1. 对于二叉树的镜像问题，很容易想到的就是使用递归来解决，自底向上依次翻转每一个节点的左右子节点，即深度优先搜索（DFS）；
2. 需要注意的是在交换节点时，需要一个临时变量来辅助交换过程。

Code

class Solution {public:    TreeNode* invertTree(TreeNode* root) {        if (nullptr == root) {            return nullptr;        }        TreeNode* temp = root->left;        root->left = invertTree(root->right);        root->right = invertTree(temp);        return root;    }};

广度优先搜索（BFS）- 辅助队列方式

1. 根据题意分析，可以转换成一个层序遍历二叉树的问题，使用队列的先入先出特性实现，来对每一层的节点进行镜像，即二叉树的广度优先搜索(BFS)；
2. 对于每一层的处理：交换当前层每个节点的左右子节点，并把当前层节点的所有子节点保存到队列中。循环执行该操作，直至结束。

Code

class Solution {public:    TreeNode* invertTree(TreeNode* root) {        if (nullptr == root) {            return nullptr;        }        queue que_node;        que_node.push(root);        while (!que_node.empty()) {            TreeNode* cur_node = que_node.front();            que_node.pop();            swap(cur_node->left, cur_node->right);            if (nullptr != cur_node->left) {                que_node.push(cur_node->left);            }            if (nullptr != cur_node->right) {                que_node.push(cur_node->right);            }        }        return root;    }};