算法
二叉树的中序迭代遍历
时间复杂度: O(n)
空间复杂度: O(h)
C++代码
class Solution {
public:
static TreeNode *convert(TreeNode *node) {
TreeNode *head = NULL;
TreeNode *prev = NULL;
stack<TreeNode *> stk;
while (node || !stk.empty()) {
while (node) {
stk.push(node);
node = node->left;
}
node = stk.top();
stk.pop();
if (head) {
prev->right = node;
node->left = prev;
} else {
head = node;
prev = node;
}
prev = node;
node = node->right;
}
return head;
}
};
Java代码
class Solution {
public static TreeNode convert(TreeNode node) {
TreeNode head = null;
TreeNode prev = null;
List<TreeNode> stk = new ArrayList<>();
while (node != null || !stk.isEmpty()) {
while (node != null) {
stk.add(node);
node = node.left;
}
node = stk.get(stk.size() - 1);
stk.remove(stk.size() - 1);
if (head != null) {
prev.right = node;
node.left = prev;
} else {
head = node;
}
prev = node;
node = node.right;
}
return head;
}
}
Python3代码
class Solution(object):
def convert(self, node):
head = None
prev = None
stk = []
while node is not None or len(stk) > 0:
while node is not None:
stk.append(node)
node = node.left
node = stk[-1]
stk.pop()
if head is not None:
prev.right = node
node.left = prev
else:
head = node
prev = node
node = node.right
return head