1. 题目描述
给定一个二叉树,返回它的中序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
2. 实现思路
迭代实现:初始化一个栈和结果数组,当栈不为空时,重复下面的步骤:
(1)将根节点和所有的左子节点放入栈中,直到没有左子节点
(2)栈顶元素出栈,存入结果数组,将出栈的元素作为根节点
(3)查看该根节点右子节点是否有左子节点,若有就入栈,否则继续出栈
3. 代码实现
/**
* 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) {
if(!root){
return [];
}
var result = []
var stack = []
while(stack.length!==0||root){
while(root){
stack.push(root);
root = root.left;
}
root = stack.pop();
result.push(root.val)
root = root.right;
}
return result;
};