X

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-解题思路分析/
Categories: leetcode
kwantong: