[LeetCode] Invert Binary Tree 翻转二叉树

た入场券 2022-04-13 21:14 207阅读 0赞

# Invert a binary tree. #

4
       /   \
      2     7
     / \   / \
    1   3 6   9

4
       /   \
      7     2
     / \   / \
    9   6 3   1

**Trivia:**  
This problem was inspired by [this original tweet][] by [Max Howell][]:

> Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

这道题让我们翻转二叉树，是树的基本操作之一，不算难题。最下面那句话实在有些木有节操啊，不知道是Google说给谁的。反正这道题确实难度不大，可以用递归和非递归两种方法来解。先来看递归的方法，写法非常简洁，五行代码搞定，交换当前左右节点，并直接调用递归即可，代码如下：

public class liubobo_7_2 {
    /// 226. Invert Binary Tree
    /// https://leetcode.com/problems/invert-binary-tree/description/
    /// 时间复杂度: O(n), n为树中节点个数
    /// 空间复杂度: O(h), h为树的高度
        // Definition for a binary tree node.
        public class TreeNode {
            int val;
            TreeNode left;
            TreeNode right;
            TreeNode(int x) { val = x; }
        }
    
        public TreeNode invertTree(TreeNode root) {
    
            if(root == null)
                return null;
    
            TreeNode left = invertTree(root.left);
            TreeNode right = invertTree(root.right);
    
            root.left = right;
            root.right = left;
    
            return root;
        }
    }

[this original tweet]: https://twitter.com/mxcl/status/608682016205344768
[Max Howell]: https://twitter.com/mxcl