94.Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]    1  /   \null   2      /    3
Output: [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; * } *//** * @param {TreeNode} root * @return {number[]} */var inorderTraversal = function(root) {  if (root) {    return [...inorderTraversal(root.left), root.val, ...inorderTraversal(root.right)]  } else {    return []  }}

颜色标记法(迭代法, 模拟系统栈)

1. 将访问过的元素标记为灰色, 未访问过的元素标记为白色;
2. 从栈顶取出访问元素:
1. 若为灰色元素, 则打印之;
2. 若为白色元素, 按照右 -> 中 -> 左的顺序推入栈, 同时将白色元素标记为灰色元素;
4    / \   2   5  / \ 1   3

white 2gray  4white 5
white 1gray  2white 3gray  4white 5
gray  1gray  2white 3gray  4white 5
white 3gray  4white 5
/** * 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) {  const printArr = []  if (!root) return printArr  const stack = []  stack.push({    color: 'white',    node: root  })
while (stack.length > 0) {    const pickValue = stack.pop()    const { color, node } = pickValue    if (color === 'gray') {      printArr.push(node.val)    } else {      node.right && stack.push({ color: 'white', node: node.right })      stack.push({ color: 'gray', node })      node.left && stack.push({ color: 'white', node: node.left })    }  }
return printArr}

144、94、145