[Algorithm] 94. Binary Tree Inorder Traversal iteratively approach _algorithm

与天地兮比寿，与日月兮齐光。这篇文章主要讲述[Algorithm] 94. Binary Tree Inorder Traversal iteratively approach相关的知识，希望能为你提供帮助。

Given a binary tree, return the inorder traversal of its nodes‘ values.
Example:

Input: [1,null,2,3] 1 2 / 3Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

/** * Definition for a binary tree node. * function TreeNode(val) { *this.val = val; *this.left = this.right = null; * } */function getLefts(root) { if (!root) { return []; }let result = []; let current = root; while(current) { result.push(current); current = current.left ; }return result; }/** * @param {TreeNode} root * @return {number[]} */ var inorderTraversal = function(root) { let lefts = getLefts(root); let result = []; while (lefts.length) { let newRoot = lefts.pop(); result.push(newRoot.val); if (newRoot.right) { let newLefts = getLefts(newRoot.right); lefts = lefts.concat(newLefts) } }return result; };

【[Algorithm] 94. Binary Tree Inorder Traversal iteratively approach】The idea is

get all the left side node and push into stack
because stack is first in last out, when we do pop(), we are actually start from bottom of the tree.
everytime, we pop one node from stack, we check its right child, get all the left nodes from this right child and append into stack.
in this way, we are able to track all the node.