leetcode 94 二叉树的中序遍历（java）_lecode中树的输入root = [1,null,3,2,4,null,5,6]是怎么转化成节点的

 

示例 1：

输入：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]

 

提示：

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

 

递归很简单粗暴，还是迭代好

package com.example.suanfa;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class three {

}


class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        LinkedList<TreeNode> tn = new LinkedList<>();
        while (root != null || !tn.isEmpty()){
            while (root != null) {
               tn.push(root);
               root = root.left;
            }
            root = tn.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
}

 class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }


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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

网上还有其他解法，如颜色标记法，莫里斯遍历。