【CT】LeetCode手撕—94. 二叉树的中序遍历

---

题目

• 原题连接：94. 二叉树的中序遍历

---

1- 思路

1-1 递归

思路1：使用递归的方式中序遍历

1-2 迭代（访问节点+处理结点）

• 思路2：使用迭代法，借助栈来实现
• 由于是中序遍历，所以第一步是 访问元素、第二部是处理元素

中序中的访问元素顺序

• 由于是中序，所以从根节点开始访问之后，第一个处理的元素应该是左子树的最左下角的元素。
• 中序中遇到的问题是：访问顺序和处理顺序不一样。

思想 ——> 利用栈，入栈采用 右 中 左的顺序，此时弹出就是 左 中 右

• 1.对于指针遍历的顺序，首先先遍历 根节点5 ——> 4 ——> 1，利用 **栈 **记录遍历的顺序
• 2. 访问到 1 的左叶子结点，发现 1的左孩子 null 了，此时从栈取元素，弹出 1
• 3. 访问道 1 的右叶子结点，发现 1的右孩子 null 了，此时从栈取元素，弹出 4
• 4. 访问 4 的右孩子，此时 4 的右孩子不为 null ，此时 入栈 2

---

2- 实现

⭐94. 二叉树的中序遍历——题解思路

①递归

class Solution {List<Integer> res = new ArrayList<>();public List<Integer> inorderTraversal(TreeNode root) {// 递归 终止条件if(root==null){return res;}// 递归逻辑inorderTraversal(root.left);res.add(root.val);inorderTraversal(root.right);return res;}
}

---

②迭代

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null){return result;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()){if (cur != null){stack.push(cur);cur = cur.left;}else{cur = stack.pop();result.add(cur.val);cur = cur.right;}}return result;}
}

---

3- ACM 实现

public class inOrder {static class TreeNode{int val;TreeNode left;TreeNode right;TreeNode(){}TreeNode(int x){val = x;}}public static TreeNode build(Integer[] nums){//借助 队列实现TreeNode root = new TreeNode(nums[0]);Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int index = 1;while(!queue.isEmpty()){TreeNode newNode = queue.poll();if(index<nums.length && nums[index]!=null){root.left = new TreeNode(nums[index]);queue.offer(root.left);}index++;if(index<nums.length && nums[index]!=null){root.right = new TreeNode(nums[index]);queue.offer(root.right);}index++;}return root;}// 中序static List<Integer> res = new ArrayList<>();public static List<Integer> inOrderT(TreeNode root){// 判空if(root==null){return res;}TreeNode cur = root;Stack<TreeNode> st = new Stack<>();while(cur!=null || !st.isEmpty()){if(cur!=null){st.push(cur);cur = cur.left;}else{cur = st.pop();res.add(cur.val);cur = cur.right;}}return res;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入二叉树构造序列");String input = sc.next();input = input.replace("[","");input = input.replace("]","");String[] part = input.split(",");Integer[] nums = new Integer[part.length];for(int i = 0 ; i < part.length;i++){if(!part[i].equals("null")){nums[i] = Integer.parseInt(part[i]);}else{nums[i] = null;}}TreeNode root = build(nums);List<Integer> forRes = inOrderT(root);System.out.println(forRes.toString());}}