企业官网建设流程全解析

翻转二叉树

题目链接：https://leetcode.cn/problems/invert-binary-tree/description/?envType=study-plan-v2&envId=top-100-liked

我的解答：

public TreeNode invertTree(TreeNode root) { if(root==null){ return null; } TreeNode temp=root.left; root.left=root.right; root.right=temp; invertTree(root.left); invertTree(root.right); return root; }

分析：代码的时间复杂度为O(n)，空间复杂度为O(n)。

看了官方题解后的解答：

//官方题解的思路与我的解题思路相同 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; }

分析：代码的时间复杂度为O(n)，空间复杂度为O(n)，使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即 O(logn)。而在最坏情况下，树形成链状，空间复杂度为 O(n)。

总结

• 本题的本质还是二叉树的深度优先搜索（递归）。