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