描述
翻转一棵二叉树。
示例：
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
1
2
3
4
5
2
3
4
5
输出：
4
/ \
7 2
/ \ / \
9 6 3 1
1
2
3
4
5
2
3
4
5
解法
因为 JS 没有二叉树的数据结构，所以新建了一个 TreeNode 的 Class，发现用 TS 写真香...
//Definition for a binary tree node.
class TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
this.val = val === undefined ? 0 : val;
this.left = left === undefined ? null : left;
this.right = right === undefined ? null : right;
}
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
递归
翻转，其实就是 Node 的左右互换。
function sortTreeNode(root: TreeNode | null): TreeNode | null {
if (root === null) return null;
let temLeft = root.left;
root.left = root.right;
root.right = temLeft;
sortTreeNode(root.left);
sortTeeeNode(root.right);
return root;
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
复杂度分析
假设树上一共 n 个节点。
- 时间复杂度：O(n)
- 空间复杂度：O(n)
总结
写递归算法的总结，关键是要明确函数的[定义]是什么，然后相信这个定义，利用这个定义来推导最终结果，绝不要跳入递归的细节中。
不在在意递归的细节，毕竟，人的脑袋才能压几个栈啊？？
写树相关的算法那，简单来说就是，先搞清楚当前 root 节点应该做什么，然后根据函数定义调用子节点，递归调用会让孩子做相同的事情。