🐷
LeetCode #94 Binary Tree Inorder Traversal
問題概要
入力値:root (num array)
出力値:num array
return the inorder traversal
問題のリンク
入力例
root: [1,null,2,3]
answer: [1,3,2]
解答例1
計算量:O(n)
DFS using recursion
Python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
def search(root, result):
if root:
search(root.left, result)
result.append(root.val)
search(root.right, result)
result = []
search(root, result)
return result
Runtime: 14ms
Beats: 55.25%
C++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
search(root, result);
return result;
}
void search(TreeNode* root, vector<int>& result) {
if (root != nullptr) {
search(root->left, result);
result.push_back(root->val);
search(root->right, result);
}
}
};
Runtime: 0ms
Beats: 100%
Discussion