理想汽车
今天看到一个帖子，挺有意思的。
先别急着骂草台班子。
像理想汽车这种情况，其实还挺常见的。
就是：面试官说出一个错误的结论，我们该咋办？
比较好的做法还是先沟通确认清楚，看看大家是否针对的为同一场景，对某些名词的认识是否统一，其实就是对错误结论的再次确认。
如果确定清楚是面试官的错误，仅做一次不直白的提醒后，看对方是否会陷入不确定，然后进入下一个问题，如果是的话，那就接着往下走。
如果对方还是揪着那个错误结论不放，不断追问。
此时千万不要只拿你认为正确的结论出来和对方辩论。
因为他只有一个结论，你也只有一个结论的话，场面就成了没有理据的争论，谁也说服不了谁。
我们可以从两个方向进行解释：
- 用逻辑进行正向推导，证明你的结论的正确性
- 用类似反证法的手段进行解释，试图从他的错误结论出发，往回推，直到推出一个对方能理解的，与常识相违背的基本知识
那么对应今天这个例子，关于「后序遍历」的属于一个定义类的认识。
我们可以用正向推导的方法，试图纠正对方。
可以从另外两种遍历方式进行入手，帮助对方理解。
比如你说：
"您看，前序遍历是「中/根 - 左 - 右」，中序遍历是「左 - 中/根 - 右」"
"所以它这个「X序遍历」的命名规则，主要是看对于一棵子树来说，根节点被何时访问。"
"所以我理解的后序遍历应该是「左 - 右 - 中/根」。"
"这几个遍历确实容易混，所以我都是这样的记忆理解的。"
大家需要搞清楚，这一段的主要目的，不是真的为了教面试官知识，因此适当舍弃一点点的严谨性，提高易懂性，十分重要。
因为我们的主要目的是：想通过有理据的解释，让他不要再在这个问题下纠缠下去。
如果是单纯想争对错，就不会有前面的「先进行友好提示，对方如果进行下一问，就接着往下」的前置处理环节。
搞清楚这一段表达的实际目的之后，你大概知道用什么口吻进行解释了，包括上述的最后一句，给对方台阶下，我觉得也是必要的。
对方是错了，但是你没必要给别人落一个「得理不饶人」的印象。
还是谦逊一些，面试场上争对错，赢没赢都是候选人输。
可能会有一些刚毕业的同学，心高气傲，觉得连二叉树这么简单的问题都搞岔的面试官，不值得被尊重。
你要知道，Homebrew 作者去面谷歌的时候，也不会翻转二叉树呢。
难道你要说这世上只有那些知识面是你知识面超集的人，才值得被尊重吗？
显然不是的，大家还是要学会带着同理心的去看待世界。
...
看了一眼，底下评论点赞最高的那位：
什么高情商说法，还得是网友。
所以面试官说的后序遍历是「右 - 左 - 中」？interesting。
...
回归主线。
也别二叉树后续遍历了，直接来个 n 叉树的后序遍历。
题目描述
平台：LeetCode
题号：590
给定一个 n 叉树的根节点 root ，返回 其节点值的后序遍历。
n 叉树在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
示例 1：
输入：root = [1,null,3,2,4,null,5,6]
输出：[5,6,3,2,4,1]
示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[2,6,14,11,7,3,12,8,4,13,9,10,5,1]
提示：
- 节点总数在范围 [0,104] 内
- 0<=Node.val<=104
- n 叉树的高度小于或等于 1000
进阶：递归法很简单，你可以使用迭代法完成此题吗?
递归
常规做法，不再赘述。
Java 代码：
class Solution {
List ans = new ArrayList<>();
public List postorder(Node root) {
dfs(root);
return ans;
}
void dfs(Node root) {
if (root == null) return;
for (Node node : root.children) dfs(node);
ans.add(root.val);
}
}
C++ 代码：
class Solution {
public:
vector<int> postorder(Node* root) {
vector<int> ans;
dfs(root, ans);
return ans;
}
void dfs(Node* root, vector<int>& ans) {
if (!root) return;
for (Node* child : root->children) dfs(child, ans);
ans.push_back(root->val);
}
};
Python 代码：
class Solution:
def postorder(self, root: 'Node') -> List[int]:
def dfs(root, ans):
if not root: return
for child in root.children:
dfs(child, ans)
ans.append(root.val)
ans = []
dfs(root, ans)
return ans
TypeScript 代码：
function postorder(root: Node | null): number[] {
const dfs = function(root: Node | null, ans: number[]): void {
if (!root) return ;
for (const child of root.children) dfs(child, ans);
ans.push(root.val);
};
const ans: number[] = [];
dfs(root, ans);
return ans;
};
- 时间复杂度：O(n)
- 空间复杂度：忽略递归带来的额外空间开销，复杂度为 O(1)
非递归
针对本题，使用「栈」模拟递归过程。
迭代过程中记录 (cnt = 当前节点遍历过的子节点数量, node = 当前节点) 二元组，每次取出栈顶元素，如果当前节点已经遍历完所有的子节点（当前遍历过的子节点数量为 cnt=子节点数量），则将当前节点的值加入答案。
否则更新当前元素遍历过的子节点数量，并重新入队，即将 (cnt+1,node) 入队，以及将下一子节点 (0,node.children[cnt]) 进行首次入队。
Java 代码：
class Solution {
public List postorder(Node root) {
List ans = new ArrayList<>();
Deque d = new ArrayDeque<>();
d.addLast(new Object[]{0, root});
while (!d.isEmpty()) {
Object[] poll = d.pollLast();
Integer cnt = (Integer)poll[0]; Node t = (Node)poll[1];
if (t == null) continue;
if (cnt == t.children.size()) ans.add(t.val);
if (cnt < t.children.size()) {
d.addLast(new Object[]{cnt + 1, t});
d.addLast(new Object[]{0, t.children.get(cnt)});
}
}
return ans;
}
}
C++ 代码：
class Solution {
public:
vector<int> postorder(Node* root) {
vector<int> ans;
stackint, Node*>> st;
st.push({0, root});
while (!st.empty()) {
auto [cnt, t] = st.top();
st.pop();
if (!t) continue;
if (cnt == t->children.size()) ans.push_back(t->val);
if (cnt < t->children.size()) {
st.push({cnt + 1, t});
st.push({0, t->children[cnt]});
}
}
return ans;
}
};
Python 代码：
class Solution:
def postorder(self, root: 'Node') -> List[int]:
ans = []
stack = [(0, root)]
while stack:
cnt, t = stack.pop()
if not t: continue
if cnt == len(t.children):
ans.append(t.val)
if cnt < len(t.children):
stack.append((cnt + 1, t))
stack.append((0, t.children[cnt]))
return ans
TypeScript 代码：
function postorder(root: Node | null): number[] {
const ans = [], stack = [];
stack.push([0, root]);
while (stack.length > 0) {
const [cnt, t] = stack.pop()!;
if (!t) continue;
if (cnt === t.children.length) ans.push(t.val);
if (cnt < t.children.length) {
stack.push([cnt + 1, t]);
stack.push([0, t.children[cnt]]);
}
}
return ans;
};
- 时间复杂度：O(n)
- 空间复杂度：O(n)
通用「非递归」
另外一种「递归」转「迭代」的做法，是直接模拟系统执行「递归」的过程，这是一种更为通用的做法。
由于现代编译器已经做了很多关于递归的优化，现在这种技巧已经无须掌握。
在迭代过程中记录当前栈帧位置状态 loc，在每个状态流转节点做相应操作。
Java 代码：
class Solution {
public List postorder(Node root) {
List ans = new ArrayList<>();
Deque d = new ArrayDeque<>();
d.addLast(new Object[]{0, root});
while (!d.isEmpty()) {
Object[] poll = d.pollLast();
Integer loc = (Integer)poll[0]; Node t = (Node)poll[1];
if (t == null) continue;
if (loc == 0) {
d.addLast(new Object[]{1, t});
int n = t.children.size();
for (int i = n - 1; i >= 0; i--) d.addLast(new Object[]{0, t.children.get(i)});
} else if (loc == 1) {
ans.add(t.val);
}
}
return ans;
}
}
C++ 代码：
class Solution {
public:
vector<int> postorder(Node* root) {
vector<int> ans;
stackint, Node*>> st;
st.push({0, root});
while (!st.empty()) {
int loc = st.top().first;
Node* t = st.top().second;
st.pop();
if (!t) continue;
if (loc == 0) {
st.push({1, t});
for (int i = t->children.size() - 1; i >= 0; i--) {
st.push({0, t->children[i]});
}
} else if (loc == 1) {
ans.push_back(t->val);
}
}
return ans;
}
};
Python 代码：
class Solution:
def postorder(self, root: 'Node') -> List[int]:
ans = []
stack = [(0, root)]
while stack:
loc, t = stack.pop()
if not t: continue
if loc == 0:
stack.append((1, t))
for child in reversed(t.children):
stack.append((0, child))
elif loc == 1:
ans.append(t.val)
return ans
TypeScript 代码：
function postorder(root: Node | null): number[] {
const ans: number[] = [];
const stack: [number, Node | null][] = [[0, root]];
while (stack.length > 0) {
const [loc, t] = stack.pop()!;
if (!t) continue;
if (loc === 0) {
stack.push([1, t]);
for (let i = t.children.length - 1; i >= 0; i--) {
stack.push([0, t.children[i]]);
}
} else if (loc === 1) {
ans.push(t.val);
}
}
return ans;
};
- 时间复杂度：O(n)
- 空间复杂度：O(n)
作者：宫水三叶的刷题日记
来源：juejin.cn/post/7327188195770351635
