【二叉树】Leetcode 266.翻转二叉树

本文主要是介绍【二叉树】Leetcode 266.翻转二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

参考文章

解题思路

        如果从整棵树的角度来看，用层序遍历翻转一棵二叉树需要遍历同一层节点后再反向遍历该层节点并且改变指针，但是这样做不仅低效率还会访问到野指针。因此必须换一个角度考虑问题：如果将每一个父节点的左右孩子交换，同样能达到翻转二叉树的效果。

        如果使用前序遍历，参考之前“前序遍历输出节点值”的代码和递归三要素：确定递归函数的参数和返回值，确定终止条件，确定单层递归的逻辑。

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

同样也可以使用层序遍历，增加一句交换左右节点即可

class Solution {
public:TreeNode* invertTree(TreeNode* root){queue<TreeNode*> temp;if(root != nullptr)temp.push(root);elsereturn root;while(!temp.empty()){int num = temp.size();for(int i = 0; i < num; i++){TreeNode* top = temp.front();temp.pop();swap(top->left, top->right);if(top->left != nullptr)     temp.push(top->left);if(top->right != nullptr)temp.push(top->right);}}}return root;
};

这篇关于【二叉树】Leetcode 266.翻转二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---