题目:
给定一个二叉树,返回它的中序 遍历。
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
抛砖引玉
思路
二叉树的中序遍历:
左子树——>根节点——>右子树
**注意:**这个遍历顺序不仅仅是遍历二叉树整体的顺序也是遍历所有子树的顺序
/**
* 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) {
let _result = []
function helper(node) {
if (!node) {
return
}
// 先深层遍历左子树
helper(node.left)
// 再遍历左子树的根节点
_result.push(node.val)
// 最后深层遍历当前根节点的右子树
helper(node.right)
}
helper(root)
return _result
}
递归方法采用了深度优先遍历的形式,一般可以采用深度优先遍历就可以采用广度优先遍历。
var inorderTraversal = function(root) {
let _result = [],
stack = []
while (root || stack.length) {
// 遍历节点左子树,入栈
while (root) {
stack.push(root)
root = root.left
}
// 节点(子树)逐个出栈,存放到结果数字
root = stack.pop()
_result.push(root.val)
// 如果出栈的是子树则同第一个有节点开始重复上面的逻辑
root = root.right
}
return _result
}
在20200808: 恢复二叉搜索树 (难度:困难)中,还遇到了Morris 中序遍历的方法
假设当前遍历到的节点为 node:
简要的讲就是,在中序遍历是在左子树走到尽头是,需要回溯到之前出现的某个节点的右节点上,就使用predecessor记录这个回溯的位置,是不存在关系的节点在遍历时连续起来。
var inorderTraversal = function(root) {
let _result = [],
predecessor = null
while (root) {
if (root.left) {
// predecessor 节点就是当前 root 节点向左走一步,然后一直向右走至无法走为止
predecessor = root.left
while (predecessor.right && predecessor.right !== root) {
predecessor = predecessor.right
}
// 让 predecessor 的右指针指向 root,继续遍历左子树
if (!predecessor.right) {
predecessor.right = root
root = root.left
}
// 说明左子树已经访问完了,我们需要断开链接
else {
_result.push(root.val)
predecessor.right = null
root = root.right
}
}
// 如果没有左孩子,则直接访问右孩子
else {
_result.push(root.val)
root = root.right
}
}
return _result
}