大纲
题目
地址
https://leetcode.com/problems/binary-tree-inorder-traversal/description/
内容
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]
Explanation:
Example 2:
Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,2,6,5,7,1,3,9,8]
Explanation:
Example 3:
Input: root = []
Output: []
Example 4:
Input: root = [1]
Output: [1]
Constraints:
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?
解题
这题就是二叉树的中序遍历。
二叉树的遍历分成三种,按照根节点的访问先后分为:
先序遍历(先根遍历):先访问根节点,然后访问左子树, 最后访问右子树。
中序遍历(中根遍历):先访问左子树,然后访问根节点, 最后访问右子树。
后序遍历(后根遍历):先访问左子树,然后访问右子树, 最后访问根节点。
代码和逻辑一样,没什么好讲的。
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
inorderTraversal(root, result);
return result;
}
private:
void inorderTraversal(TreeNode* root, vector<int>& result) {
if (root == nullptr) return;
inorderTraversal(root->left, result);
result.push_back(root->val);
inorderTraversal(root->right, result);
}
};
代码地址
https://github.com/f304646673/leetcode/tree/main/94-Binary-Tree-Inorder-Traversal
标签:Binary,遍历,inorderTraversal,Tree,Example,访问,result,root,94 From: https://blog.csdn.net/breaksoftware/article/details/142109158