二叉树的中序遍历

题目描述

给定一个二叉树的根节点 root，返回 它的 中序 遍历。

示例 1： 输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2： 输入：root = []
输出：[]

示例 3： 输入：root = [1]
输出：[1]

思路&js代码

1、递归

var inorderTraversal = function(root) {
    const res = [];
    const inorder = (root) => {
        if (!root) {
            return;
        }
        inorder(root.left);
        res.push(root.val);
        inorder(root.right);
    }
    inorder(root);
    return res;
};
 

2、迭代

var inorderTraversal = function(root) {
    const res = [];
    const stk = [];
    while (root || stk.length) {
        while (root) {
            stk.push(root);
            root = root.left;
        }
        root = stk.pop();
        res.push(root.val);
        root = root.right;
    }
    return res;
};