欢迎访问LeetCode题解合集
题目描述
给定一个二叉树的根节点 root
,返回它的 中序 遍历。
示例 1:
[HTML_REMOVED]
[HTML_REMOVED]
输入:root = [1,null,2,3]
输出:[1,3,2]
示例 2:
输入:root = []
输出:[]
示例 3:
输入:root = [1]
输出:[1]
示例 4:
[HTML_REMOVED]
[HTML_REMOVED]
输入:root = [1,2]
输出:[2,1]
示例 5:
[HTML_REMOVED]
[HTML_REMOVED]
输入:root = [1,null,2]
输出:[1,2]
提示:
- 树中节点数目在范围
[0, 100]
内 - $-100 \le Node.val \le 100$
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
题解:
二叉树中序遍历顺序:左子树、根节点、右子树。
法一:
递归。
先递归左子树,将根节点值加入答案,在递归右子树。
时间复杂度:$O(n)$
额外空间复杂度:$O(n)$
/**
* 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> ret;
void inorder(TreeNode* root) {
if ( root ) {
inorder( root->left );
ret.emplace_back( root->val );
inorder( root->right );
}
}
vector<int> inorderTraversal(TreeNode* root) {
inorder( root );
return ret;
}
};
/*
时间:0ms,击败:100.00%
内存:8.2MB,击败:81.82%
*/
法二:
迭代。
将 方法一 中的递归用非递归实现,因为递归过程中系统隐式地维护了一个栈,我们在迭代的时候需要显示地将这个栈模拟出来。
时间复杂度:$O(n)$
额外空间复杂度:$O(n)$
/**
* 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;
stack<TreeNode*> stk;
while ( stk.size() || root ) {
while ( root ) {
stk.push( root );
root = root->left;
}
root = stk.top();
stk.pop();
ret.push_back( root->val );
root = root->right;
}
return ret;
}
};
/*
时间:0ms,击败:100.00%
内存:8.2MB,击败:82.80%
*/
法三:
Morris 遍历。
普通遍历的额外空间复杂度为 $O(h)$,h
为二叉树高度。因为每个节点都有指向孩子节点的指针,所以从上层到下层容易,但是没有指向父节点的指针,所以从下层到上层需要用栈来辅助完成。
而 Morris
遍历的牛逼之处在于:通过让底层节点指向 null
的空闲指针指向上层的某个节点,从而完成从下层到上层的移动。避免了使用栈结构,这种方法可以把额外空间复杂度优化到 $O(1)$。
Morris
遍历的实现原则,记当前的节点为 cur
:
-
如果
cur
无左孩子,cur
向右移动(cur = cur.right
) -
如果
cur
有左孩子,找到cur
左子树上最右的节点,记为mostright
:
1.如果mostright
的right
指针指向空,让其指向cur
,cur
向左移动(cur = cur.left
)
2.如果mostright
的right
指针指向cur
,让其指向空,cur
向右移动(cur = cur.right
)
/**
* 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;
TreeNode *cur = root, *mostright = nullptr;
while ( cur ) {
if ( !cur->left ) {
ret.emplace_back( cur->val );
cur = cur->right;
} else {
mostright = cur->left;
while ( mostright->right && mostright->right != cur )
mostright = mostright->right;
if ( mostright->right == cur ) {
ret.emplace_back( cur->val );
mostright->right = nullptr;
cur = cur->right;
} else {
mostright->right = cur;
cur = cur->left;
}
}
}
return ret;
}
};
/*
时间:0ms,击败:100.00%
内存:8.1MB,击败:92.20%
*/