#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);
}
}
Reference
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.
Top comments (0)