记录贴，互勉

冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲冲

中序遍历只写出递归的方法，应该是不会被面试官轻易放过的。很可能让你写迭代的方法，两种都熟练面试官就很满意了。如果你能写出时间O(N) ，空间 O(1)的迭代方法就更好了

337. House Robber III
Medium
经典题目: take or not take
For the current root node, we can either take or not take, we use a recursive function to calculate the maximum value we can get, we start from the bottom to the top, if we take current node, the child couldn't be take, but the grandchild could be either take or not take.
In this question, we need to use memory to prevent multiple calculations.
As the bottom node already calculated once for its best result, we just need to check whether we take the root value or not take but the maximum value of its left and right child.

Uses a recursion helper function to call itself
94. Binary Tree Inorder Traversal
Left -> Root -> Right
144. Binary Tree Preorder Traversal
Root -> Left -> Right
145. Binary Tree Postorder Traversal
Left -> Right -> Root
429. N-ary Tree Level Order Traversal
Use Queue to  do level order, In order to get all the value from
the same level, we need to add all the children of the current root to the queue

补充内容 (2023-08-16 10:05 +08:00):

lishuzheng1012 发表于 2023-8-15 18:16
中序遍历只写出递归的方法，应该是不会被面试官轻易放过的。很可能让你写迭代的方法，两种都熟练面试官就很 ...

谢谢提醒

微信用户_b99d1cc 发表于 2023-8-15 18:00
Uses a recursion helper function to call itself
94. Binary Tree Inorder Traversal
Left -> Root ->  ...

94. Binary Tree Inorder Traversal    Space O(1)做法
Use stack to add all the current left node to the stack until hit the null, then add the current
value to the ans, then check the right subTree.

144. Binary Tree Preorder Traversal

这不是space O(1)，给一颗一直往左走的树，这个代码第一件事就是把所有节点压栈里去，O(1)那个叫Morris Traversal

aodeyyoyo 发表于 2023-8-16 06:18
这不是space O(1)，给一颗一直往左走的树，这个代码第一件事就是把所有节点压栈里去，O(1)那个叫Morris Tra ...

恩 后面发现问题了哈哈哈 太久没刷题了

429. N-ary Tree Level Order Traversal
Use Queue
589. N-ary Tree Preorder Traversal
use helper function (recursion)

微信用户_b99d1cc 发表于 2023-8-19 06:27
429. N-ary Tree Level Order Traversal
Use Queue
589. N-ary Tree Preorder Traversal

590. N-ary Tree Postorder Traversal
Recursive