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

示例

示例 1：

image.png

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

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[2,1]

示例 5：

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

题解

建立一个栈，遍历树，遇到节点将节点推入栈中，以例1为例

第一次遍历到 ① 节点，推入栈
stack = [①] res = []

遍历 ① 节点的左子节点，如果是 null 则将 stack 推出一个节点，获取 val 值
stack = [] res = [1]

遍历 ① 节点的右子节点，推入栈，如果有节点推入栈
stack = [②] res = [1]

遍历 ② 的 左子节点，推入栈
stack = [② ③] res = [1]

遍历 ③ 节点的左子节点，如果是 null 则将 stack 推出一个节点，获取 val 值
stack = [②] res = [1,3]

遍历 ③ 节点的右子节点，如果有节点推入栈，如果没有节点， 将 stack 推出一个节点，获取 val 值
stack = [] res = [1,3,2]

总体的流程是，优先遍历左子节点，如果有一直入栈。等到没有左子节点时，栈中推出一个节点（获取它的父节点）记录值。然后判断父节点的右子节点是否有值，重复以上动作

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} root
  11.  * @return {number[]}
  12.  */
  13. var inorderTraversal = function(root) {
  14.     if (!root) {
  15.         return []
  16.     }
  17.     const stack = []
  18.     const res = []
  19.     let cur = root
  21.     while(stack.length || cur) {
  22.         if (cur) {
  23.             stack.push(cur)
  24.             cur = cur.left
  25.         } else {
  26.             cur = stack.pop()
  27.             res.push(cur.val)
  28.             cur = cur.right
  29.         }
  30.     }
  31.     return res
  32. };

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。