Re:Invert a binary tree on LeetCode
by tjscanlon on Saturday June 13, 2015 @06:36AM
(#9710570)
Iterative solution:
[ Parent
| on HN ]
Re:Invert a binary tree on LeetCode
by TheLoneWolfling on Saturday June 13, 2015 @11:14AM
(#9711242)
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.Any particular reason why you're using an array as a stack (LIFO) but calling it "queue" (FIFO)?
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 :)
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)))