255.LeetCode | 94. 二叉树的中序遍历

vlambda
2021-03-08

255.LeetCode | 94. 二叉树的中序遍历

每天一个开发小知识

题目

给定一个二叉树的根节点 root

返回它的中序遍历

思路

没想到最后一道树题目竟然如此简单

直接使用中序遍历即可

通过这段时间集中解决树题目

总结了处理树的四种方法

解法：中序遍历

时间复杂度 O(n)，空间复杂度 O(1)

/** * 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> ret; Do(root, ret); return ret; }
    void Do(TreeNode * node, vector<int> & ret) { if (NULL == node) { return; }
 Do(node->left, ret); ret.push_back(node->val); Do(node->right, ret); }};