给定一个二叉树,返回它的中序 遍历。

示例:

1
2
3
4
5
6
7
8
输入: [1,null,2,3]
1
\
2
/
3

输出: [1,3,2]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

个人解答

方法一:递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
const res = []
traversal(root, res)
return res
};
function traversal (root, res) {
if (root) {
if (root.left) {
traversal(root.left, res)
}
res.push(root.val)
if (root.right) {
traversal(root.right, res)
}
}
}

方法而:栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var inorderTraversal = function(root) {
var res = []
var stack = []

while (root || stack.length) {
if (root.left) { // 如果有左节点先遍历左节点
stack.push(root)
root = root.left
} else if (!root.left && !root.right) { // 既没有左节点也没有右节点
res.push(root.val)
root = stack.pop() // 回溯
root && (root.left = null)
} else if (root.right) { // 如果有右节点
res.push(root.val)
root = root.right
}
}

return res
}
解题思路

https://jangdelong.github.io/blog_img/images/leetcode-94/1.png

  • 前序遍历:先输出根节点,在依次前序遍历左子树和右子树;

  • 中序遍历:先中序遍历左子树,在输出根节点,最后中序遍历右子树;

  • 后序遍历:先后序遍历左子树,接着后序遍历右子树,最后输出根节点。

输出

前序遍历:1,2,4,5,3,6,7;

中序遍历:4,2,5,1,3,7,6

后序遍历:4,5,2,7,6,3,1