LeetCode 94.二叉树的中序遍历 Java实现中序遍历左子树 → 根节点 → 右子树二叉树节点定义javaclass TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val val;this.left left;this.right right;}}解法1递归javaimport java.util.ArrayList;import java.util.List;class Solution {public List inorderTraversal(TreeNode root) {List ans new ArrayList();dfs(root, ans);return ans;}private void dfs(TreeNode node, ListInteger ans) { if (node null) return; dfs(node.left, ans); // 左 ans.add(node.val); // 根 dfs(node.right, ans); // 右 }}解法2迭代栈非递归javaimport java.util.ArrayList;import java.util.List;import java.util.Stack;class Solution {public List inorderTraversal(TreeNode root) {List ans new ArrayList();Stack stack new Stack();TreeNode cur root;while (cur ! null || !stack.isEmpty()) { // 一直往左走全部入栈 while (cur ! null) { stack.push(cur); cur cur.left; } cur stack.pop(); ans.add(cur.val); cur cur.right; } return ans; }}解法3Morris 中序遍历O(1)额外空间利用线索二叉树不使用栈仅临时修改树结构遍历完毕复原javaimport java.util.ArrayList;import java.util.List;class Solution {public List inorderTraversal(TreeNode root) {List ans new ArrayList();TreeNode cur root;while (cur ! null) {if (cur.left null) {ans.add(cur.val);cur cur.right;} else {// 找左子树最右节点TreeNode pre cur.left;while (pre.right ! null pre.right ! cur) {pre pre.right;}if (pre.right null) {pre.right cur;cur cur.left;} else {pre.right null;ans.add(cur.val);cur cur.right;}}}return ans;}}复杂度递归时间O(n)空间O(h)h为树高栈迭代时间O(n)空间O(h)Morris时间O(n)空间O(1)需要 Python / Rust / C 版本吗