leetcode：Invert Binary Tree
2024-10-13 06:27:17
Invert a binary tree.
4
/ \
2 7
/ \ / \
1 3 6 9
to
4
/ \
7 2
/ \ / \
9 6 3 1
即反转二叉树，代码如下：
/**
* 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 { //在每一层将节点的左孩子和右孩子分别交换即可，直到节点没有孩子（递归recursion）
public:
TreeNode* invertTree(TreeNode* root) {
TreeNode *temp;
if(root)
{
temp = root->right;
root->right = invertTree(root->left);
root->left = invertTree(temp);
}
return root;
}
};
或者：
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root) {
root->left = invertTree(root->left), root->right = invertTree(root->right);
std::swap(root->left, root->right);
}
return root;
}
};
其他解法：
1、C++ using queue, 0ms
非递归版本，做广度优先处理，使用一个队列来保存当前水平未处理的非空节点。每次，切换前节点的左，右指针，将其弹出，并添加它的非空孩子到队列中。
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root==nullptr) return nullptr;
queue<TreeNode*> st;
st.push(root);
while(!st.empty()){
TreeNode* n=st.front();
st.pop();
if (n->left!=NULL)
st.push(n->left);
if (n->right!=NULL)
st.push(n->right);
swap(n->left,n->right);
}
return root;
}
};
2、先前序遍历这棵树的每个结点，如果遍历到的结点有子节点，就交换他的两个子节点，当交换完所有非叶子节点的左右子节点之后，就得到了该二叉树的镜像。
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root==null){
return null;
}
if(root->left==null&&root->right==null){
return root;
}
TreeNode *temp = root->left;
root->left = root->right;
root->right = temp;
if(root->left!=null){
invertTree(root->left);
}
if(root->right!=null){
invertTree(root->right);
}
return root;
}
};
显示出错：‘null’ was not declared in this scope
将null改为nullptr就 Accepted了：
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root==nullptr){
return nullptr;
}
if(root->left==nullptr&&root->right==nullptr){
return root;
}
TreeNode *temp = root->left;
root->left = root->right;
root->right = temp;
if(root->left!=nullptr){
invertTree(root->left);
}
if(root->right!=nullptr){
invertTree(root->right);
}
return root;
}
};
【C++11】nullptr关键字：从1972年C语言刚刚诞生以来，常数0就扮演着整数（int）0和空指针（ null pointer ）两种角色。为了避免理解上的二义性，C语言通常使用NULL宏来表示空指针，NULL宏通常被定义为(void *)0或0， 而C++仅仅采用0来表示空指针，这样存在一个问题：比如对于重载函数 fun(char *) 和 fun(int) 的调用来说，若直接用NULL作为参数调用fun(NULL)，我们可能认为NULL作为空指针的表示，应该调用 fun(char *) 函数，然而NULL实际上的值为0，就会调用 fun(int) 。 nullptr 关键字正是为了解决这一问题而产生的。
nullptr 能够转换成任何指针类型（包括成员函数指针和成员变量指针）和bool类型（这是为了兼容普通指针都能使用 if(ptr) 判断是否为空指针的形式），但是不能被转换为整数0。
（更多了解可参考：http://blog.csdn.net/huang_xw/article/details/8764346）
最新文章
- vs2012 发布web应用程序
- CentOS添加163源
- 20. 星际争霸之php设计模式--适配器模式
- springmvc权限过滤器
- 代码风格与树形DP
- WPF 超链接方式
- openstack fe
- GC的代机制
- android中实现“再按一次退出”功能
- poj 3411 Paid Roads
- POJ - 3666 Making the Grade（dp+离散化）
- Windows下python安装MySQLdb
- java线程控制方法
- MySQL表空间集
- HBase：Shell
- PHP simpleXML文件编程
- Linux 学习笔记_12_文件共享服务_2_FTP应用--vsftpd
- JavaScript构造函数
- springMVC的配置与使用
- canvas-9NonZeroAroundPrinciples2.html