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

示例:

1
2
3
4
5
6
7
8
输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

个人解答

方法一：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 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 res = []
  traversal(root, res)
  return res
};
function traversal (root, res) {
  if (root) {
    if (root.left) {
      traversal(root.left, res)
    }
    res.push(root.val)
    if (root.right) {
      traversal(root.right, res)
    }
  }
}

方法而：栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var inorderTraversal = function(root) {
  var res = []
  var stack = []
  
  while (root || stack.length) {
  	if (root.left) { // 如果有左节点先遍历左节点
  	  stack.push(root)
  	  root = root.left
  	} else if (!root.left && !root.right) { // 既没有左节点也没有右节点
  	  res.push(root.val)
  	  root = stack.pop() // 回溯
  	  root && (root.left = null)
  	} else if (root.right) { // 如果有右节点
  	  res.push(root.val)
  	  root = root.right
  	}
  }
  
  return res
}
解题思路

https://jangdelong.github.io/blog_img/images/leetcode-94/1.png

  • 前序遍历：先输出根节点，在依次前序遍历左子树和右子树；

  • 中序遍历：先中序遍历左子树，在输出根节点，最后中序遍历右子树；

  • 后序遍历：先后序遍历左子树，接着后序遍历右子树，最后输出根节点。

输出

前序遍历：1，2，4，5，3，6，7；

中序遍历：4，2，5，1，3，7，6

后序遍历：4，5，2，7，6，3，1