每一个节点恰好被遍历一次
发布时间：2025-06-24 17:06:41 作者：北方职教升学中心 阅读量：289
空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别
迭代方式：
class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<>(); while (root != null || !stack.isEmpty()) { while (root != null) { stack.push(root); root = root.left; } root = stack.pop(); res.add(root.val); root = root.right; } return res; }}子循环中root遍历到root左子树最深层次过程中，依次将左结点压栈，左结点为空退出子循环，将栈顶元素出栈， root=root.right重新进入大循环既可遍历该树所有结点。中序遍历和后序遍历的简单递归方法不附图讲解，主要解释它们的迭代方式及层序遍历
1、- 中序遍历（左根右）
首先遍历左子树，然后访问根结点，最后遍历右子树。前序遍历
递归方式：
迭代方式：
2、
- 后序遍历（左右根）
首先遍历左子树，然后遍历右子树，最后访问根结点。
4、递归方式
class Solution { List<List<Integer>> result=new ArrayList<>(); public List<List<Integer>> levelOrder(TreeNode root) { order(root,0); return result; } public void order(TreeNode node,int deep) { if(node==null)return; deep++; if(result.size()<deep) { List<Integer> item=new ArrayList<>(); result.add(item); } result.get(deep-1).add(node.val); order(node.left,deep); order(node.right,deep); }}
class Solution { List<List<Integer>> result=new ArrayList<>(); public List<List<Integer>> levelOrder(TreeNode root) { order(root,0); return result; } public void order(TreeNode node,int deep) { if(node==null)return; deep++; if(result.size()<deep) { List<Integer> item=new ArrayList<>(); result.add(item); } result.get(deep-1).add(node.val); order(node.left,deep); order(node.right,deep); }}在方法void order(TreeNode node,int deep) ，传相应的结点和二维数组下标，设置节点对应位置
加图理解：
时间复杂度；O(n)
迭代方式：
代码设计重点：出栈既遍历。该结点无右结点 2、
class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); postorder(root, res); return res; } public void postorder(TreeNode root, List<Integer> res) { if (root == null) { return; } postorder(root.left, res); postorder(root.right, res); res.add(root.val); }}复杂度分析
时间复杂度：O(n)，其中 n 是二叉搜索树的节点数。
空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。进入子循环前，用size记录栈内元素，进入子循环后，依次将栈顶元素弹出，同时将不为空的左右结点入，size--；
class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res=new ArrayList<>(); if(root==null) return res; Queue<TreeNode> queue=new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ int size=queue.size(); List<Integer> list=new ArrayList<>(); while(size--!=0){ TreeNode top=queue.poll(); list.add(top.val); if(top.left!=null) queue.offer(top.left); if(top.right!=null) queue.offer(top.right); } res.add(list); } return res; }}时间复杂度；O(n)
二叉树的遍历结束
