rust golang 数据结构 后端 算法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>>,

// pub right: Option>>,

// }

//

// 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>>) -> Vec {

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 inorderTraversal(TreeNode* root) {

vector 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 inorderTraversal(TreeNode root) {

List ans = new ArrayList();

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;

}

}

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

推荐链接

 您阅读本篇文章共花了：