# 94. Binary Tree Inorder Traversal

Given a binary tree, return the  inorder  traversal of its nodes’ values.

Example:

``````Input: [1,null,2,3]
1
\
2
/
3

Output: [1,3,2]
``````

Follow up: Recursive solution is trivial, could you do it iteratively?

``````class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> res;
inorder(root, res);
return res;
}
void inorder(TreeNode *root, vector<int> &res) {
if (!root) return;
if (root->left) inorder(root->left, res);
res.push_back(root->val);
if (root->right) inorder(root->right, res);
}
};
``````

``````// Non-recursion
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> res;
stack<TreeNode*> s;
TreeNode *p = root;
while (p || !s.empty()) {
while (p) {
s.push(p);
p = p->left;
}
p = s.top(); s.pop();
res.push_back(p->val);
p = p->right;
}
return res;
}
};
``````

``````class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
TreeNode *p = root;
while (!s.empty() || p) {
if (p) {
s.push(p);
p = p->left;
} else {
p = s.top(); s.pop();
res.push_back(p->val);
p = p->right;
}
}
return res;
}
};
``````

A binary tree is  threaded  by making all right child pointers that would normally be null point to the inorder successor of the node ( if  it exists), and all left child pointers that would normally be null point to the inorder predecessor of the node.

1. 初始化指针 cur 指向 root

2. 当 cur 不为空时

- 如果 cur 没有左子结点

a) 打印出 cur 的值

b) 将 cur 指针指向其右子节点

- 反之

将 pre 指针指向 cur 的左子树中的最右子节点

* 若 pre 不存在右子节点

a) 将其右子节点指回 cur

b) cur 指向其左子节点

* 反之

a) 将 pre 的右子节点置空

b) 打印 cur 的值

c) 将 cur 指针指向其右子节点

``````class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> res;
if (!root) return res;
TreeNode *cur, *pre;
cur = root;
while (cur) {
if (!cur->left) {
res.push_back(cur->val);
cur = cur->right;
} else {
pre = cur->left;
while (pre->right && pre->right != cur) pre = pre->right;
if (!pre->right) {
pre->right = cur;
cur = cur->left;
} else {
pre->right = NULL;
res.push_back(cur->val);
cur = cur->right;
}
}
}
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/94

Validate Binary Search Tree

Binary Tree Preorder Traversal

Binary Tree Postorder Traversal

Binary Search Tree Iterator

Kth Smallest Element in a BST

Closest Binary Search Tree Value II

Inorder Successor in BST

https://leetcode.com/problems/binary-tree-inorder-traversal/

https://leetcode.com/problems/binary-tree-inorder-traversal/discuss/31231/c-ierative-recursive-and-morris-traversal

https://leetcode.com/problems/binary-tree-postorder-traversal/discuss/45551/preorder-inorder-and-postorder-iteratively-summarization

https://leetcode.com/problems/binary-tree-postorder-traversal/discuss/45621/preorder-inorder-and-postorder-traversal-iterative-java-solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation