iOS实现反转二叉树

前言

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运行结果

总结

反转二叉树的题目也是算法中比较基础的题目,笔者在这里只是通过递归的方法进行实现,其他的方法大家可以自己研究下,欢迎讨论.另外笔者认为算法可能不会在实际开发中真正用到,但是却能锻炼开发者的思维能力,能更好的去分析解决问题,这也是为什么现在许多大公司都喜欢考算法题的原因吧.