3 ms·

Iterative solution: def invertTree(self, root): queue = [] if root is not None: queue.append(root) while queue:

Iterative solution: def invertTree(self, root): queue = [] if root is not None: queue.append(root) while queue: current = queue.pop() current.left, current.right = current.right, current.left if current.left is not None: queue.append(current.left) if current.right is not None: queue.append(current.right) return root

seivan 11y ago
Not sure why, but I'd feel iffy iterating on a list while mutating its content. But I guess it's file while ignoring the order of the items, and just caring if it's containing items or empty. Carry on :)
- ICWiener 11y ago
  A functional approach: (defun mirror (tree) (when tree (tree (tree-data tree) (mirror (tree-right tree)) (mirror (tree-left tree))))) For completness, here are the definitions: (defpackage :trees (:use :cl) (:shadow #:copy-tree)) (in-package :trees) (defstruct (tree (:constructor tree (data &optional left right)) (:type list)) data left right) As well as a test case: (mirror (tree 4 (tree 2 (tree 1) (tree 3)) (tree 7 (tree 6) (tree 9)))) => (4 (7 (9 NIL NIL) (6 NIL NIL)) (2 (3 NIL NIL) (1 NIL NIL)))
cousin_it 11y ago
Any particular reason why you're using an array as a stack (LIFO) but calling it "queue" (FIFO)?
TheLoneWolfling 11y ago
Better solution: def invertTree(self, root): queue = [] if root is not None: queue.append(root) while current is not None or len(queue) > 0: while current is None: current = queue.pop() current.left, current.right = current.right, current.left if current.left is not None: if current.right is not None: queue.append(current.right) current = current.left else: current = current.right return root No needless enqueuing / dequeuing of things unless you need to. As a bonus, if the nodes maintain a count of how many children the have overall you can always recurse on the smaller child first and use less memory.

seivan 11y ago

Not sure why, but I'd feel iffy iterating on a list while mutating its content. But I guess it's file while ignoring the order of the items, and just caring if it's containing items or empty. Carry on :)

ICWiener 11y ago
A functional approach: (defun mirror (tree) (when tree (tree (tree-data tree) (mirror (tree-right tree)) (mirror (tree-left tree))))) For completness, here are the definitions: (defpackage :trees (:use :cl) (:shadow #:copy-tree)) (in-package :trees) (defstruct (tree (:constructor tree (data &optional left right)) (:type list)) data left right) As well as a test case: (mirror (tree 4 (tree 2 (tree 1) (tree 3)) (tree 7 (tree 6) (tree 9)))) => (4 (7 (9 NIL NIL) (6 NIL NIL)) (2 (3 NIL NIL) (1 NIL NIL)))

cousin_it 11y ago

Any particular reason why you're using an array as a stack (LIFO) but calling it "queue" (FIFO)?

TheLoneWolfling 11y ago

Better solution: def invertTree(self, root): queue = [] if root is not None: queue.append(root) while current is not None or len(queue) > 0: while current is None: current = queue.pop() current.left, current.right = current.right, current.left if current.left is not None: if current.right is not None: queue.append(current.right) current = current.left else: current = current.right return root No needless enqueuing / dequeuing of things unless you need to. As a bonus, if the nodes maintain a count of how many children the have overall you can always recurse on the smaller child first and use less memory.