需求
Bonus points if you could solve it both recursively and iteratively.
我做过的最难的Easy题目。
算法
中序迭代遍历二叉树
时间复杂度: O(n)
空间复杂度: O(h)
C++代码
class Solution {
public:
static bool isSymmetric(TreeNode *root) {
if (!root) {
return true;
}
TreeNode *node0 = root->left;
TreeNode *node1 = root->right;
stack<TreeNode *> stk0;
stack<TreeNode *> stk1;
while (node0 || node1 || !stk0.empty() || !stk1.empty()) {
while (node0 && node1) {
stk0.push(node0);
node0 = node0->left;
stk1.push(node1);
node1 = node1->right;
}
if (node0 || node1) {
return false;
}
node0 = stk0.top();
stk0.pop();
node1 = stk1.top();
stk1.pop();
if (node0->val != node1->val) {
return false;
}
node0 = node0->right;
node1 = node1->left;
}
return true;
}
};
Java代码
class Solution {
public static boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
TreeNode node0 = root.left;
TreeNode node1 = root.right;
List<TreeNode> stk0 = new ArrayList<>();
List<TreeNode> stk1 = new ArrayList<>();
while (node0 != null || node1 != null || !stk0.isEmpty() || !stk1.isEmpty()) {
while (node0 != null && node1 != null) {
stk0.add(node0);
node0 = node0.left;
stk1.add(node1);
node1 = node1.right;
}
if (node0 != null || node1 != null) {
return false;
}
node0 = stk0.get(stk0.size() - 1);
stk0.remove(stk0.size() - 1);
node1 = stk1.get(stk1.size() - 1);
stk1.remove(stk1.size() - 1);
if (node0.val != node1.val) {
return false;
}
node0 = node0.right;
node1 = node1.left;
}
return true;
}
}
Python3代码
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root:
return True
node0 = root.left
node1 = root.right
stk0 = []
stk1 = []
while node0 or node1 or stk0 or stk1:
while node0 and node1:
stk0.append(node0)
node0 = node0.left
stk1.append(node1)
node1 = node1.right
if node0 or node1:
return False
node0 = stk0.pop()
node1 = stk1.pop()
if node0.val != node1.val:
return False
node0 = node0.right
node1 = node1.left
return True