二叉树的中序遍历

[JesseZhao1990]

方法一：利用递归

/**
 * 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) { 
     function loop(node,arr){
        if(node === null) return;
             if(node.left){
                 loop(node.left,arr)
             }
             arr.push(node.val)
             if(node.right){
                 loop(node.right,arr)
             }
     }
     var res = [];
     loop(root,res);
     return res;
       
};

方法二： 利用栈

/**
 * 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) { 
    var res = [];
    var stack = [];
    
    while(true){
        while(root){
            stack.push(root)
            root = root.left;
        }
        
        if(stack.length===0) break;
        let node = stack.pop();
        if(node !== null){
           res.push(node.val);
           root = node.right; 
        }
        
    }
    
    return res;
    
       
};

LeetCode原题地址：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/description/