LeetCode 94. Binary Tree Inorder Traversal (With Java)

先附上题目连结

问题说明:给定的一棵树，透过一个List(Int型态)来储存此树中序的遍历

树的遍历(Traversal)可以分成:
1. 前序(Preorder)
2. 中序(Inorder)
3. 后序(Postorder)
4. 层序(Level-order)

此题要探讨的是中序的遍历。

Inorder探讨：首先，我们要先拜访的是左边的节点，之后再拜访父节点，最后再拜访右边的节点。总体来说，我们每次都要尽可能的走到最左边，直到左边没有节点(也就是Null)，之后我们才会到上一层(也就是父节点)，接着继续往右拜访，顺序就是左-->中-->右。用文字来描述可能太过于抽象，以下会用例子来进行说明。

*图片来源:维基百科的Binary tree

以此图来说，它的Inorder traversal就是1-->3-->4-->6-->7-->8-->10-->13-->14
说明:从根节点8开始，有左节点3，持续拜访，而3又有左节点1，但是1没有节点了，因此1为第一个，之后回到3(第二个)，3有右节点6，而6有左节点4，4没有其他节点(第三个)，回到6(第四个)，6有右节点7而且7没有其他节点，因此7在第五个，之后回到6再回到3再回到8，8为第六个，8有右节点10(第七个)，10没有左节点但有右节点14，14有左节点13因此13在第八个回到14，结束此次遍历。

虚拟码(表达概念，不同程式语言要考虑其语法转换)

inorderTraversal(Tree root){if(root==null) return;else{    inorderTraversal(root.left);//拜访左边节点    print(root.val)//印出root的值，如果是要用list来储存每个节点的值可以换成 list.add(root.val)    inorderTraversal(root.right);//拜访右边节点    }}

在此题当中，我会使用一个List来储存树的资料并运用递迴概念来进行回传
程式码加上说明

/** * Definition for a binary tree node. * public 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; *     } * } */class Solution {    List<Integer> l=new ArrayList<>();//建立一个List进行储存    public List<Integer> inorderTraversal(TreeNode root) {        if(root==null){return l;}//如果根节点本身就没有东西，则直接回传List l        else{            inorderTraversal(root.left);//拜访左边节点            l.add(root.val);//List新增中间节点的值            inorderTraversal(root.right);//拜访右边节点        }        return l;//回传    }}

之后会持续讲解其他LeetCode的题目