题干
[力扣-二叉树的中序遍历]
题干详见 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; }
|