算法leetcode｜94.二叉树的中序遍历（多语言实现）

---

文章目录 94. 二叉树的中序遍历：样例 1：样例 2：样例 3：提示： 分析：题解：rust：go：c++：python：java：

---

94. 二叉树的中序遍历：

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

样例 1：

输入： root = [1,null,2,3] 输出： [1,3,2] 样例 2： 输入： root = [] 输出： [] 样例 3： 输入： root = [1] 输出： [1] 提示： 树中节点数目在范围 [0, 100] 内-100 <= Node.val <= 100

---

分析： 面对这道算法题目，二当家的再次陷入了沉思。二叉树的中序遍历和前序遍历，后续遍历是二叉树常用的遍历方式。使用递归方式比循环非递归方式更加简单，直观，易于理解。通常二叉树的中序遍历一定要使用一个栈结构，因为中序遍历的要求是遍历完左子树才能遍历当前节点，但是遍历到了左子树就无法再回到当前节点了，所以一般都是使用压栈的方式，先将当前节点压栈，遍历完左子树再将当前节点出栈，这样空间复杂度就会是 O(n) （递归也相当于使用了栈结构）。说起来这不是什么大问题，但是算法就是要想办法优化降低时间和空间的复杂度，于是寄出一种可以将空间复杂度降低为 O(1) 的中序遍历方式，Morris 中序遍历。事实上Morris 中序遍历不是没有代价的，由于要做额外的节点连接和恢复，相当于用时间换空间。

---

题解： rust： // Definition for a binary tree node. // #[derive(Debug, PartialEq, Eq)] // pub struct TreeNode { // pub val: i32, // pub left: Option<Rc<RefCell<TreeNode>>>, // pub right: Option<Rc<RefCell<TreeNode>>>, // } // // impl TreeNode { // #[inline] // pub fn new(val: i32) -> Self { // TreeNode { // val, // left: None, // right: None // } // } // } use std::rc::Rc; use std::cell::RefCell; impl Solution { pub fn inorder_traversal(mut root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> { let mut ans = Vec::new(); while root != None { if root.as_ref().unwrap().borrow().left != None { // 寻找当前 root 节点的前驱节点：前驱 predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止 let mut predecessor = root.as_ref().unwrap().borrow().left.clone(); while predecessor.as_ref().unwrap().borrow().right != None && predecessor.as_ref().unwrap().borrow().right != root { predecessor = predecessor.unwrap().borrow().right.clone(); } if predecessor.as_ref().unwrap().borrow().right == None { // 让前驱 predecessor 节点的右指针指向当前 root 节点，继续遍历左子树，之后会再次回到当前 root 节点 predecessor.unwrap().borrow_mut().right = root.clone(); // 遍历左子树 root = root.unwrap().borrow().left.clone(); continue; } else { // 左子树遍历完毕又回到了当前 root 节点，让前驱 predecessor 节点的右指针与当前 root 节点断开，恢复原样 predecessor.unwrap().borrow_mut().right = None; } } // 遍历当前 root 节点 ans.push(root.as_ref().unwrap().borrow().val); // 遍历当前 root 节点的右子树 root = root.unwrap().borrow().right.clone(); } return ans; } }

---

go： /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func inorderTraversal(root *TreeNode) []int { var ans []int for root != nil { if root.Left != nil { // 寻找当前 root 节点的前驱节点：前驱 predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止 predecessor := root.Left for predecessor.Right != nil && predecessor.Right != root { // 有右子树且没有设置过指向 root，则继续向右走 predecessor = predecessor.Right } if predecessor.Right == nil { // 让前驱 predecessor 节点的右指针指向当前 root 节点，继续遍历左子树，之后会再次回到当前 root 节点 predecessor.Right = root // 遍历左子树 root = root.Left continue } else { // 左子树遍历完毕又回到了当前 root 节点，让前驱 predecessor 节点的右指针与当前 root 节点断开，恢复原样 predecessor.Right = nil } } // 遍历当前 root 节点 ans = append(ans, root.Val) // 遍历当前 root 节点的右子树 root = root.Right } return ans }

---

c++： /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> ans; while (root != nullptr) { if (root->left != nullptr) { // 寻找当前 root 节点的前驱节点：前驱 predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止 TreeNode *predecessor = root->left; while (predecessor->right != nullptr && predecessor->right != root) { predecessor = predecessor->right; } if (predecessor->right == nullptr) { // 让前驱 predecessor 节点的右指针指向当前 root 节点，继续遍历左子树，之后会再次回到当前 root 节点 predecessor->right = root; // 遍历左子树 root = root->left; continue; } else { // 左子树遍历完毕又回到了当前 root 节点，让前驱 predecessor 节点的右指针与当前 root 节点断开，恢复原样 predecessor->right = nullptr; } } // 遍历当前 root 节点 ans.emplace_back(root->val); // 遍历当前 root 节点的右子树 root = root->right; } return ans; } };

---

python： # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: ans = list() while root is not None: if root.left is not None: # 寻找当前 root 节点的前驱节点：前驱 predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止 predecessor = root.left while predecessor.right is not None and predecessor.right != root: # 有右子树且没有设置过指向 root，则继续向右走 predecessor = predecessor.right if predecessor.right is None: # 让前驱 predecessor 节点的右指针指向当前 root 节点，继续遍历左子树，之后会再次回到当前 root 节点 predecessor.right = root # 遍历左子树 root = root.left continue else: # 左子树遍历完毕又回到了当前 root 节点，让前驱 predecessor 节点的右指针与当前 root 节点断开，恢复原样 predecessor.right = None # 遍历当前 root 节点 ans.append(root.val) # 遍历当前 root 节点的右子树 root = root.right return ans

---

java： /** * Definition for a binary tree node. * public class 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; * } * } */ class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> ans = new ArrayList<Integer>(); while (root != null) { if (root.left != null) { // 寻找当前 root 节点的前驱节点：前驱 predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止 TreeNode predecessor = root.left; while (predecessor.right != null && predecessor.right != root) { predecessor = predecessor.right; } if (predecessor.right == null) { // 让前驱 predecessor 节点的右指针指向当前 root 节点，继续遍历左子树，之后会再次回到当前 root 节点 predecessor.right = root; // 遍历左子树 root = root.left; continue; } else { // 左子树遍历完毕又回到了当前 root 节点，让前驱 predecessor 节点的右指针与当前 root 节点断开，恢复原样 predecessor.right = null; } } // 遍历当前 root 节点 ans.add(root.val); // 遍历当前 root 节点的右子树 root = root.right; } return ans; } }

---

非常感谢你阅读本文~ 欢迎【点赞】【收藏】【评论】三连走一波~ 放弃不难，但坚持一定很酷~ 希望我们大家都能每天进步一点点~ 本文由 二当家的白帽子： le-yi.blog.csdn.net/ 博客原创~

---