038翻转二叉树

翻转二叉树题目链接https://leetcode.cn/problems/invert-binary-tree/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答public TreeNode invertTree(TreeNode root) { if(rootnull){ return null; } TreeNode temproot.left; root.leftroot.right; root.righttemp; invertTree(root.left); invertTree(root.right); return root; }分析代码的时间复杂度为O(n)空间复杂度为O(n)。看了官方题解后的解答//官方题解的思路与我的解题思路相同 public TreeNode invertTree(TreeNode root) { if(rootnull){ return null; } TreeNode left invertTree(root.left); TreeNode right invertTree(root.right); root.leftright; root.rightleft; return root; }分析代码的时间复杂度为O(n)空间复杂度为O(n)使用的空间由递归栈的深度决定它等于当前节点在二叉树中的高度。在平均情况下二叉树的高度与节点个数为对数关系即 O(logn)。而在最坏情况下树形成链状空间复杂度为 O(n)。总结本题的本质还是二叉树的深度优先搜索递归。