# 一. 基础
# 二. 刷题
注意：一般不会只要求写递归，一般要求使用迭代，更甚者使用 Morris 遍历
- 树的中序遍历
解析：拿遍历左子树来说，遍历到左子树结束时候，此时 stk=[1,2,4],出栈（执行步骤 9），root=4,stk=[1,2],res=[4],root=null(执行到了步骤 11)。第二次遍历，root 为空，步骤 5 不执行，到步骤 9，root=2,stk=[1],res=[4,2],root=5。第三次遍历，root 为 5，步骤 5 执行，stk=[1,5]，往下执行，root=[5],res=[4,2,5]...
//迭代
1 var inorderTraversal = function(root) {
2 const res = [];
3 const stk = [];
4 while (root || stk.length) {
5 while (root) {
6 stk.push(root);
7 root = root.left;
8 }
9 root = stk.pop();
10 res.push(root.val);
11 root = root.right;
12 }
13 return res;
14 };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
- 将有序数组转换为二叉搜索树
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var sortedArrayToBST = function(nums) {
const buildTree = (Arr, left, right) => {
if (left > right) return null;
let mid = Math.floor(left + (right - left) / 2);
let root = new TreeNode(Arr[mid]);
root.left = buildTree(Arr, left, mid - 1);
root.right = buildTree(Arr, mid + 1, right);
return root;
};
return buildTree(nums, 0, nums.length - 1);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
- 递归三步曲分析：
① 明确递归函数的参数和返回值
② 明确终止条件
③ 明确单层递归的逻辑
求深度适合用前序遍历，而求高度适合用后序遍历。
看到 https://www.pzijun.cn/algorithms/tree/6.html 怀疑人生：刷算法的初衷是什么呢？为什么要执着于刷算法？一看就会一写就废