leetcode226. 翻转二叉树
程序员文章站
2022-05-18 14:36:06
...
写在前面
这道题是在阿里面试时,手撕代码的题目。刚开始用递归实现了,面试官进一步要求,能否用循环的形式实现。
- 递归实现时,递归结束的判断条件冗余(刚开始写了两个判断条件,节点为空的时候返回,节点为叶子节点的时候返回,其实没有必要对节点是叶子节点的时候进行判断)
leetcode226. 翻转二叉树
翻转一棵二叉树。
示例:
输入:
4
/ \
2 7
/ \ / \
1 3 6 9
输出:
4
/ \
7 2
/ \ / \
9 6 3 1
备注:
这个问题是受到 Max Howell 的 原问题 启发的 :
谷歌:我们90%的工程师使用您编写的软件(Homebrew),但是您却无法在面试时在白板上写出翻转二叉树这道题,这太糟糕了。
完整代码
后序遍历递归形式
/**
* 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 {
public:
TreeNode* invertTree(TreeNode* root) {
if(root == NULL)
return root;
TreeNode * Lnode = invertTree(root->left);
TreeNode * Rnode = invertTree(root->right);
root->left = Rnode;
root->right = Lnode;
return root;
}
};
非递归实现:中序遍历形式
/**
* 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 {
public:
TreeNode* invertTree(TreeNode* root) {
if(root == NULL)
return root;
TreeNode* p = root;
stack<TreeNode*> st;
while(!st.empty() || p){
while(p){
st.push(p);
p = p->left;
}
p = st.top();
st.pop();
//交换
TreeNode * temp = p->right;
p->right = p->left;
p->left = temp;
p = p->right;
}
return root;
}
};
后续遍历非递归形式实现:
注意:什么时候节点出栈?只有当该节点的左右孩子交换完后,才出栈
/**
* 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 {
public:
TreeNode* invertTree(TreeNode* root) {
if(root == NULL)
return root;
TreeNode* p = root, *pre;
stack<TreeNode*> st;
while(!st.empty() || p){
while(p){
st.push(p);
p = p->left;
}//p是最左面的节点
p = st.top();
if(p->right == NULL || p->right == pre){//右孩子为空,右孩子已经交换完
TreeNode * temp = p->right;
p->right = p->left;
p->left = temp;
pre = p;
p = NULL;
st.pop();
}
else{
p = p->right;
pre = NULL;
}
}
return root;
}
};
先序遍历非递归形式:
简单来讲:将访问节点修改成交换节点的左右子树
/**
* 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 {
public:
TreeNode* invertTree(TreeNode* root) {
if(root == NULL)
return root;
TreeNode* p = root, *pre;
stack<TreeNode*> st;
while(!st.empty() || p){
while(p){
st.push(p);
TreeNode * temp = p->right;
p->right = p->left;
p->left = temp;
p = p->left;
}//p是最左面的节点
p = st.top();
st.pop();
p = p->right;
}
return root;
}
};
总结:这道题的本质:将 二叉树中先序、中序、后序遍历二叉树中访问节点的代码 改成 交换节点的左右子树的代码就OK。
下一篇: 去旅行如何打包行李?