二叉树的中序遍历|算法专题
# 题目
给定一个二叉树，返回它的 中序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
@前端进阶之旅: 代码已经复制到剪贴板
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
# 代码
递归实现
var inorderTraversal = function (root, array = []) {
if (root) {
inorderTraversal(root.left, array);
array.push(root.val);
inorderTraversal(root.right, array);
}
return array;
};
@前端进阶之旅: 代码已经复制到剪贴板
非递归实现
- 取根节点为目标节点，开始遍历
- 1.左孩子入栈 -> 直至左孩子为空的节点
- 2.节点出栈 -> 访问该节点
- 3.以右孩子为目标节点，再依次执行1、2、3
var inorderTraversal = function (root) {
const result = [];
const stack = [];
let current = root;
while (current || stack.length > 0) {
while (current) {
stack.push(current);
current = current.left;
}
current = stack.pop();
result.push(current.val);
current = current.right;
}
return result;
};
@前端进阶之旅: 代码已经复制到剪贴板
