前言
Max Howell大家可能都知道,他是著名的HomeBrew的作者,却在面试谷歌时由于不会写反转二叉树被谷歌拒绝.所以笔者抱着学习的态度在LeetCode上找到了Max Howell那道很有名的反转二叉树题目,比较简单适合刚接触算法的开发者们,所以笔者用OC和Swift分别进行了实现.原题地址
题目:
Input:
4
/ \
2 7
/ \ / \
1 3 6 9
Output:
4
/ \
7 2
/ \ / \
9 6 3 1
首先分析下这个二叉树,从上往下看发现这个树是把树上的数据进行了交换,但是仔细一看发现最后一排的1-3反转过去后变成了3-1.所以得出结论,这道题是左右子树进行了交换,用函数递归就能很容易实现了.
知道了如何实现,直接看代码:
OC版本
声明节点属性
@interface TreeNode : NSObject
@property (nonatomic, assign) NSInteger val;
@property (nonatomic, strong) TreeNode *left;
@property (nonatomic, strong) TreeNode *right;
@end
实现代码:
- (void)exchangeNode:(TreeNode *)node {
//判断是否存在node节点
if(node) {
//交换左右节点
TreeNode *temp = node.left;
node.left = node.right;
node.right = temp;
}
}
- (TreeNode *)invertTree:(TreeNode *)root
{
//边界条件 递归结束或输入为空情况
if(!root) {
return root;
}
//递归左右子树
[self invertTree:root.left];
[self invertTree:root.right];
//交换左右子节点
[self exchangeNode:root];
return root;
}
OC运行结果
Swift版本
节点
public class TreeNode {
public var val: Int
public var left: TreeNode?
public var right: TreeNode?
public init(_ val: Int) {
self.val = val
self.left = nil
self.right = nil
}
}
实现代码:
func invertTree(_ root: TreeNode?) -> TreeNode? {
guard let root = root else {
return nil
}
invertTree(root.left)
invertTree(root.right)
exchangeNode(root)
return root;
}
func exchangeNode(_ node: TreeNode?) {
if node != nil {
let tmp = node?.left
node?.left = node?.right
node?.right = tmp
}
}
Swift运行结果
总结
反转二叉树的题目也是算法中比较基础的题目,笔者在这里只是通过递归的方法进行实现,其他的方法大家可以自己研究下,欢迎讨论.另外笔者认为算法可能不会在实际开发中真正用到,但是却能锻炼开发者的思维能力,能更好的去分析解决问题,这也是为什么现在许多大公司都喜欢考算法题的原因吧.
