094.二叉树的中序遍历

2021-04-19

题目

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

示例 1：
 1
  \
  2
 /
3  
输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：
输入：root = []
输出：[]

示例 3：
输入：root = [1]
输出：[1]

示例 4：
   1
  / 
2
输入：root = [1,2]
输出：[2,1]

示例 5：
1 
  \ 
    2
输入：root = [1,null,2]
输出：[1,2]

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶:

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

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

思路

中序遍历：左 -> 根 -> 右

JS实现

1、递归实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var helper = function (root, result) {
  if (root != null) {
    if (root.left != null) {
      helper(root.left, result);
    }
    result.push(root.val);
    if (root.right != null) {
      helper(root.right, result);
    }
  }
};

var inorderTraversal = function (root) {
  const result = [];
  if (root === null) {
    return result;
  }
  helper(root, result);
  return result;
};

2、迭代实现

var inorderTraversal = function (root) {
  const result = [];
  if (root === null) {
    return result;
  }

  // 栈的特点：先进后出
  const stack = [];

  // 设当前节点为根节点
  let curr = root;

  while (curr != null || stack.length > 0) {
    // 递归获取当前节点的左节点，并入栈
    while (curr != null) {
      stack.push(curr);
      curr = curr.left;
    }
    // 出栈
    curr = stack.pop();
    // 保存当前元素的值
    result.push(curr.val);
    // 设当前节点为右节点
    curr = curr.right;
  }
  return result;
};

Go实现

package main

import (
  "fmt"
)

type TreeNode struct {
  Val   int       // 根
  Left  *TreeNode //左节点
  Right *TreeNode //右节点
}

func main() {
  /*
         1
      2        3
    21    22    31  32
  */

  node1 := TreeNode{Val: 1}
  node2 := TreeNode{Val: 2}
  node3 := TreeNode{Val: 3}

  node21 := TreeNode{Val: 21}
  node22 := TreeNode{Val: 22}
  node31 := TreeNode{Val: 31}
  node32 := TreeNode{Val: 32}

  node1.Left = &node2
  node1.Right = &node3

  node2.Left = &node21
  node2.Right = &node22
  node3.Left = &node31
  node3.Right = &node32

  fmt.Println(inorderTraversal1(&node1))
  fmt.Println(inorderTraversal2(&node1))
}

func inorderTraversal1(root *TreeNode) (res []int) {
  var inorder func(node *TreeNode)
  inorder = func(node *TreeNode) {
    if node == nil {
      return // 结束当前递归
    }
    inorder(node.Left)          // 遍历左子树
    res = append(res, node.Val) // 添加根节点到数组里
    inorder(node.Right)         // 遍历右子树
  }
  inorder(root)
  return
}

func inorderTraversal2(root *TreeNode) (res []int) {
  // 定义一个栈，栈存的就是一棵树
  stack := []*TreeNode{}

  for root != nil || len(stack) > 0 {
    for root != nil {
      //先根节点，再把所有的左子树入栈
      stack = append(stack, root)
      root = root.Left
    }
    //因为先进后出，拿到了最下面的左节点
    root = stack[len(stack)-1]
    //出栈
    stack = stack[:len(stack)-1]
    //保存结果
    res = append(res, root.Val)
    //再把所有的右子树入栈
    root = root.Right
  }
  return
}