题目描述
题目链接:94. Binary Tree Inorder Traversal
Given the root
of a binary tree, return the inorder traversal of its nodes' values.
例子
例子 1
Input: root = [1,null,2,3] Output: [1,3,2]
例子 2
Input: root = [] Output: []
例子 3
Input: root = [1] Output: [1]
例子 4
Input: root = [1,2] Output: [2,1]
例子 5
Input: root = [1,null,2] Output: [1,2] Explanation:
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?
解题思路
这道题要求输出二叉树的中序遍历,同样可以利用栈来解决。首先不停往栈中压入所有左节点(相当于树的最左侧),然后从栈顶取出节点再取其右节点进行重复操作。代码如下:
#include <stack>
#include <vector>
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
std::vector<int> result;
if (!root) return result;
std::stack<TreeNode*> s;
TreeNode* curr = root;
while (!s.empty() || curr) {
while (curr) {
s.push(curr);
curr = curr->left;
}
curr = s.top();
s.pop();
result.push_back(curr->val);
curr = curr->right;
}
return result;
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(h)
GitHub 代码同步地址: 94.BinaryTreeInorderTraversal.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions