Binary Tree Inorder Traversal

#algorithms #csharp #leetcode #easy

#94.Binary Tree Inorder Traversal

Problem statement

Given the root of a binary tree, return the inorder traversal of its nodes' values.

Example 1

Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2

Input: root = []
Output: []

Example 3

Input: root = [1]
Output: [1]

Explanation

給定一個二元樹，返回中序走訪的節點值

Solution

解題前先來了解中序走訪，樹的走訪是訪問樹中所有節點，並將樹中的資料轉換成線性關係，例如返回一個結果陣列。那麼中序走訪的順序是先訪問左子樹，接著是樹根，最後才是右子樹，依照左子樹→樹根→右子樹的順序走訪二元樹直到葉節點也就是終端節點為止

此題意思非常清楚，單純只是寫一個中序走訪的遞迴方法，建立一個集合 res 用來儲存每次走訪的節點值，另外再建立一個 Inorder 的方法，其方法內容為中序走訪的方式，先判斷節點是否為 null，如果為 null 則代表這個節點是終點節點，所以不做任何事；若該節點為非 null，則先呼叫 Inorder 自己，參數帶入左節點，透過遞迴左子樹直到終端節點為止，當抵達終端節點時，Inorder 方法判斷該節點為 null，不做任何事結束方法，並返回到呼叫自己的方法，此時再將節點值記錄到 res 裡，接著再用相同作法走訪右子樹

public IList<int> InorderTraversal(TreeNode root)
{
    IList<int> res = new List<int>();
    Inorder(root, ref res);
    return res;
}

private void Inorder(TreeNode node, ref IList<int> res)
{
    if (node != null)
    {
        Inorder(node.left, ref res);
        res.Add(node.val);
        Inorder(node.right, ref res);
    }
}