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

---

文章目录

• 94. 二叉树的中序遍历：
• 分析：
• 题解：

---

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;
    }
}

---

---