【递归】【前序中序后序遍历】【递归调用栈空间与二叉树深度有关】Leetcode 94 144 145

---------------🎈🎈题目链接 前序遍历🎈🎈-------------------
---------------🎈🎈题目链接 中序遍历🎈🎈-------------------
---------------🎈🎈题目链接 后序遍历🎈🎈-------------------

1.前序遍历（递归） preorder

时间复杂度分析：
对于每个节点，只访问它一次。因此，时间复杂度是 O(n)，其中 n 是二叉树中节点的数量。
空间复杂度分析：
在递归调用过程中，使用了一个辅助列表来存储节点的值。
最坏情况下，二叉树是一个单链的情况，即树的深度等于节点数量n，递归调用栈的深度即为n，此时空间复杂度是 O(n)。
综上所述，时间复杂度是 O(n)，空间复杂度是 O(n)。

⭐️递归调用栈的大小和二叉树的深度有关！
在Java中，递归调用栈（Recursion Call Stack）是指在执行递归函数时，系统自动为每次函数调用分配的内存空间。每当函数被调用时，相关的局部变量、参数和返回地址等信息都会被存储在栈内存中，直到函数执行完毕并返回结果，然后系统会释放这些内存空间。

当一个函数在执行过程中调用了自身（或者间接调用了其他函数，形成了递归循环）时，会导致递归调用栈的深度增加。每次递归调用都会向栈内存中压入一帧（Frame），表示一个函数调用的信息，包括函数的参数、局部变量和返回地址等。当递归调用结束时，对应的帧会从栈顶弹出，释放相应的内存空间。

递归调用栈在处理递归算法时非常重要，它可以帮助跟踪每次递归调用的状态，确保递归函数能够正确地返回结果。然而，需要注意的是，递归调用栈的深度是有限的，如果递归的层数过深，可能会导致栈溢出（Stack Overflow）错误。因此，在编写递归函数时，需要谨慎考虑递归的深度和递归终止条件，以避免栈溢出错误。

时间复杂度O(N)
空间复杂度O(N)

2.中序遍历（递归）inorder

时间复杂度O(N)
空间复杂度O(N)

3.后序遍历（递归）postorder

时间复杂度O(N)
空间复杂度O(N)