4 ms·
It means to swap the left and right arm of each node. So you effectively "mirror" the tree.
by gizmo 9y ago
It means to swap the left and right arm of each node. So you effectively "mirror" the tree.
- ezekg 9y agoYeah, it's relatively simple once you come to that realization: TreeNode* invertTree(TreeNode* root) { if (root == NULL) { return NULL; } TreeNode* tmp = invertTree(root->left); root->left = invertTree(root->right); root->right = tmp; return root; } It sounds a lot more complicated than it is.
- vkou 9y agoUntil I throw this test case at you: TreeNode testRoot = new TreeNode(); testRoot.left = testRoot; invertTree(root); // Stack overflow. But that's not a tree, that's a cyclic graph, you may shout. That's true, but you still need to sanity-check your inputs.
- archagon 9y agoThat ought to be done in a separate validation step, and/or the tree object should enforce its invariants. (I shouldn’t be arguing interview problems on HN, but I’ve had a few beers.)
- vkou 9y agoI argue that if an interview question asks you to implement parseInt(String foo), it's your responsibility to handle inputs that aren't a properly formatted integer gracefully. Or at least to point out to the interviewer that your solution fails to handle unexpected input, and ask if they want you to add input validation logic, or if they are satisfied with the answer.
- archagon 9y agoSure, but this assumes that foo is a valid String — just formatted incorrectly for use with an int. If we can't assume that TreeNode constitutes a valid (cycle-free) tree, we essentially have to embed a full cycle-checker in our otherwise simple inversion function. I would argue that goes against the intent of the question.