二叉树的中序遍历-中等
难度：中等
题目描述：
给定一个二叉树，返回它的*中序 *遍历。
示例：
输入: [1, null, 2, 3];
1;
\;
2 / 3;
输出: [1, 3, 2];
1
2
3
4
5
6
2
3
4
5
6
解题思路：
递归法:
var inorderTraversal = function (root) {
let result = [];
const pushRoot = (root) => {
if (root !== null) {
if (root.left != null) {
pushRoot(root.left);
}
result.push(root.val);
if (root.right != null) {
pushRoot(root.right);
}
}
};
pushRoot(root);
return result;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
迭代法：
中序遍历，先要将最左边的节点全部加入栈中，然后逐个 pop 出来
核心思想注意，将右子树重置为 root，进行下一步的循环。
两个 while 嵌套，中间的就是继续存放子树的节点
var inorderTraversal = function (root) {
let arr = [];
let stackArr = [];
while (root != null || stackArr.length != 0) {
while (root != null) {
stackArr.push(root);
root = root.left;
}
root = stackArr.pop();
arr.push(root.val);
root = root.right;
}
return arr;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14