LeetCode 226. Invert Binary Tree(翻转二叉树)
题目描述
Invert a binary tree.
4
/ \
2 7
/ \ / \
1 3 6 9
to
4
/ \
7 2
/ \ / \
9 6 3 1
解法一
思路
这是一道经典题目了,自从Max Howell面试Google没有写出来这道题,就吸引了更高的人气了。
注意观察示例可以发现,简单来说反转二叉树就是对每个结点来说,调换左右子结点的位置,所以其实就是一个简单的二叉树遍历。那么二叉树的前序、中序和后序遍历里面该用哪种呢?可以看到每次操作(对于某个结点)只与“左”子结点和“右”子结点相关,即不影响“左右”的位置关系即可,所以这里用前序和后序遍历都可以。为什么不能用中序遍历?拿示例用中序遍历模拟一下就明白啦~
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if root is None:
return
self.invertTree(root.left)
self.invertTree(root.right)
root.left, root.right = root.right, root.left
return root
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
invertTree(root.left);
invertTree(root.right);
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
return root;
}
}
C++
/**
* 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 == nullptr) {
return nullptr;
}
invertTree(root->left);
invertTree(root->right);
TreeNode *temp = root->left;
root->left = root->right;
root->right = temp;
return root;
}
};