lc面试准备:Invert Binary Tree

1 题目

Invert a binary tree.


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

to

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

接口: public TreeNode invertTree(TreeNode root)

2 思路

反转一颗二叉树。

可以用递归和非递归两种方法来解。

  • 递归的方法,写法非常简洁,五行代码搞定,交换当前左右节点,并直接调用递归即可。
  • 非递归的方法,参考树的层序遍历,借助Queue来辅助,先把根节点排入队列中,然后从队中取出来,交换其左右节点,如果存在则分别将左右节点在排入队列中,以此类推直到队列中木有节点了停止循环,返回root即可。

复杂度:两种方法的时间和空间复杂度一样,Time O(n);Space O(n)

3 代码

  • 思路1:
        public TreeNode invertTree(TreeNode root) {
if (root == null)
return root;
TreeNode tmp = root.left;
root.left = invertTree(root.right);
root.right = invertTree(tmp);
return root;
}

4 总结

考察二叉树的遍历。

非递归的实现,复习。请实现非递归。

5 参考

上一篇:javascript检测当前客户端


下一篇:[ASP.NET Core 3.1]浏览器嗅探解决部分浏览器丢失Cookie问题