DEV Community

Cover image for Binary Tree Inorder Traversal
FakeStandard
FakeStandard

Posted on

Binary Tree Inorder Traversal

#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]
Enter fullscreen mode Exit fullscreen mode

Example 2

Input: root = []
Output: []
Enter fullscreen mode Exit fullscreen mode

Example 3

Input: root = [1]
Output: [1]
Enter fullscreen mode Exit fullscreen mode

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);
    }
}
Enter fullscreen mode Exit fullscreen mode

Reference

LeetCode Solution

GitHub Repository


Thanks for reading the article 🌷 🌻 🌼

If you like it, please don't hesitate to click heart button ❤️
or click like on my Leetcode solution
or follow my GitHub
or buy me a coffee ⬇️ I'd appreciate it.

Buy-me-a-coffee


Top comments (0)