LEETCODE 226. Invert Binary Tree 解题思路分析

题目大意：

翻转二叉树

翻转一棵二叉树。

示例：

输入：

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

输出：

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

备注:
这个问题是受到 Max Howell 的 原问题 启发的 ：

谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=226

解题思路分析：

就像上面推文中提到的，如果你不会翻转二叉树，那真是太糟糕了。对于二叉树的题目，我们多次强调过你应该首先想到使用dfs深度优先搜索来解题。本题我们从根节点开始向下进行dfs递归，如果当前节点为空，则返回空。反之则分别dfs递归至左右子节点，dfs的返回值也分别代表左右两个子节点left和right（翻转后的左右子树），接下来我们做当前节点下的翻转操作，即将当前节点的左子节点设置为right，右子节点设置为left，最后返回当前节点。

实现代码：

public TreeNode invertTree(TreeNode root) {
    if(root==null) return null; // 如果当前节点为空，返回空
    TreeNode right=invertTree(root.right); // 递归至右子节点，获得翻转后的右子树
    TreeNode left=invertTree(root.left); // 递归至左子节点，获得翻转后的左子树
    root.right=left; // 将右子节点设置为左子节点
    root.left=right; // 将左子节点设置为右子节点
    return root; // 返回将当前节点
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Invert Binary Tree.

Memory Usage: 36.6 MB, less than 5.10% of Java online submissions for Invert Binary Tree.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-226-invert-binary-tree-解题思路分析/