给定一个二叉树的根节点 root ,返回它的 中序 遍历 。
示例 1:
输入:root = [1,null,2,3] 输出:[1,3,2] 示例 2: 输入:root = [] 输出:[] 示例 3: 输入:root = [1] 输出:[1]
提示:
- 树中节点数目在范围 [0, 100] 内
- -100 <= Node.val <= 100
迭代实现:
vector<int> inorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> st; while (!st.empty() || root) { while (root) { st.push(root); root = root->left; } root = st.top(); st.pop(); res.push_back(root->val); root = root->right; } return res; }
递归实现:
void helper(TreeNode* root, vector<int> &res) { if (root->left) helper(root->left, res); res.push_back(root->val); if (root->right) helper(root->right, res); } vector<int> inorderTraversal(TreeNode* root) { if (!root) return {}; vector<int> res; helper(root, res); return res; }
mirrors 算法:
设当前节点为 cur
没有左节点
直接遍历右节点
有左节点
找到左节点的最右的子节点
如果最右节点的右节点为空 (最右节点的右节点不一定为空,因为我们会令它指向 cur 节点)
令右节点指向 cur, 遍历 cur 的左节点
如果最右节点的右节点不为空,说明 cur 的左节点已经遍历完
断开最右节点和 cur 的连接,开始遍历 cur 的右节点
vector<int> inorderTraversal(TreeNode* root) { vector<int> res; while (root) { if (root->left) { // 此时的 root 表示 cur 节点 TreeNode* rightmost = root->left; while (rightmost->right && rightmost->right != root) { rightmost = rightmost->right; //找到左节点的最右节点 } if (rightmost->right) { // 最右节点的右节点不为空,cur 节点的左节点遍历完 res.push_back(rightmost->right->val); root = root->right; rightmost->right = nullptr; } else { // 最右节点为空,令其指向 root,开始遍历左节点 rightmost->right = root; root = root->left; } } else { // 左节点为空,直接遍历右节点 res.push_back(root->val); root = root->right; } } return res; }