代码随想录

LeetCode 144. 二叉树的前序遍历

LeetCode 145. 二叉树的后序遍历

LeetCode 94. 二叉树的中序遍历

carl

二叉树遍历 #递归

思路

• 递归的写法：CS 106b中关于递归的写法：

  • base case
  • recursive case

• 迭代的写法：

  • 栈
  • 迭代

细节

• 递归与栈+迭代的对应关系

• 递归

• 迭代（部分节点入栈）

  • 前序（p空说明中节点访问完且左子树访问完，接着开始访问右子树）
    • ![[Pasted image 20221025220447.png]]
    • ![[Pasted image 20221025221332.png]]
    • ![[Pasted image 20221025222246.png]]
    • ![[Pasted image 20221025222123.png]]
  • 后序（p空 说明访问完左子树，如果右子树也空或已访问，则右树访问完，可以访问中节点；否则右子树还未访问，就访问右子树）
    • ![[Pasted image 20221025231856.png]]
    • 中序（p为空时，说明左子树访问完，可以访问中节点，接着开始访问右子树）
      • ![[Pasted image 20221025233201.png]]

• 迭代（全部节点入栈）

  • 前序
    • ![[Pasted image 20221025222816.png]]
  • 后序
    • 依然按前序，但左右调换，生成后再将数组逆置