题目描述:
一句话,翻转一棵二叉树。
原题备注:
这个问题是受到 Max Howell 的 原问题 启发的 :
谷歌:我们90%的工程师使用您编写的软件(Homebrew),但是您却无法在面试时在白板上写出翻转二叉树这道题,这太糟糕了。
解题思路:
我想应该有两种办法,第一种是递归,也是第一反应,第二种就是迭代。
递归法:先进行递归结束的条件判断。然后分别对左右子树进行递归,然后将左右子树互换位置即可。
迭代法:类似深度优先搜索的方式,采用队列存储未访问过的节点,分别将左右子树的节点进行位置互换,然后将节点的子节点存入队列。然后从队列中取出未访问的节点,进行翻转。每个节点只会进入一次队列,所以时间复杂度也是O(n)。
中文官网题解:
https://leetcode-cn.com/problems/invert-binary-tree/solution/
个人题解:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Solution { public TreeNode invertTree(TreeNode root) { if(null == root) return null; else{ TreeNode left = invertTree(root.left); TreeNode right = invertTree(root.right); root.left = right; root.right = left; return root; } }}
结果:
简单,所以快。