二叉树的中序遍历-力扣94 中序遍历

题干

题干详见 LeetCode ，图片过多不在此赘述。

递归

思路

首先分析题干，迷惑了我半天的示例原来是这个类：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0 , TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

不得不说这代码弄得我是…血压升高又没得办法

1
2
3
4
5
6
7
8
9
public int Val { get; set;}
public TreeNode Left { get; set;}
public TreeNode Right { get; set;}

public TreeNode(int val = 0 , TreeNode left = null, TreeNode right = null) {
    Val = val;
    Left = left;
    Right = right;
}

另外这种构造函数似乎没有必要写，因为可以使用类似于：

1
2
3
4
5
var node = new TreeNode()
{
    Val = 5,
    Left = chileLeft,
};

这种代码来完成。一般情况下用构造函数是属性不可为空的情况下。

跑题了（）

首先啥是二叉树，这玩意离散数学应该讲过，~~但是我没听（x）~~ 二叉树是一个树形结构，每个节点有两个子节点。中序遍历就是先遍历左面的，再来他本身然后是右面的。递归的话不深究他的细节，写就完了。

首先来个判空避免 NullReferenceException ，对于递归来说我们只需要负责好其中的环节就好了，至于细节千万不要深究，比较脑瓜子没几层栈，想了没两下就 StackOverflow 了。

那么在这个方法中，先添加左，再添加他本身，然后右节点，返回即可。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public IList<int> InorderTraversal(TreeNode root)
{
    if (root is null) return new List<int>();

    var result = new List<int>();

    // 实际上不需要判空
    // 递归左
    result.AddRange(InorderTraversal(root.left));

    result.Add(root.val);

    // 递归右
    result.AddRange(InorderTraversal(root.right));

    return result;
}