## 知识点

### 二叉树遍历

**前序遍历**：**先访问根节点**，再前序遍历左子树，再前序遍历右子树

**中序遍历**：先中序遍历左子树，**再访问根节点**，再中序遍历右子树

**后序遍历**：先后序遍历左子树，再后序遍历右子树，**再访问根节点**

注意点

- 以根访问顺序决定是什么遍历

- 左子树都是优先右子树

#### 前序递归

```c++

void preorderTraversal(TreeNode *root) {

if (!root) {

return;

}

cout << root->val << " ";

preOrderTraversal(root->left);

preOrderTraversal(root->right);

}

```

#### 前序非递归

```c++

void preorderTraversal(TreeNode *root) {

if (!root) {

return;

}

auto stack = vector<TreeNode *>();

while (root || !stack.empty()) {

if (!root) {

root = stack.back();

stack.pop_back();

}

cout << root->val << " ";

if (root->right) {

stack.push_back(root->right);

}

root = root->left;

}

}

```

#### 中序非递归

```c++

void inorderTraversal(TreeNode *root) {

if (!root) {

return;

}

auto stack = vector<TreeNode *>();

while (root || !stack.empty()) {

while (root) {

stack.push_back(root);

root = root->left;

}

root = stack.back();

stack.pop_back();

cout << root->val << " ";

root = root->right;

}

}

```

#### 后序非递归

```c++

void postorderTraversal(TreeNode *root) {

if (!root) {

return;

}

auto stack = vector<TreeNode *>();

TreeNode *lastPop = nullptr;

while (root || !stack.empty()) {

// 每次找到最左下节点

while (root) {

stack.push_back(root);

root = root->left;

}

root = stack.back();

// 后序遍历，不能直接弹出，先检查是否有右子节点

// 右节点要注意有可能已经遍历过了，又撤回来到当前节点

// 只要保存上次弹出的节点即可！上次弹出的必定是其右子节点

if (root->right && root->right != lastPop) {

root = root->right;

continue;

}

cout << root->val << " ";

stack.pop_back();

lastPop = root;

root = nullptr;

}

}

```

注意点

- 核心就是：根节点必须在右节点弹出之后，再弹出

#### DFS 深度搜索-从上到下

```c++

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

};

vector<int> preOrderTraversal(TreeNode *root) {

vector<int> result;

dfs(root, result);

return result;

}

void dfs(TreeNode *root, vector<int> &result) {

if (!root) {

return;

}

result.push_back(root->val);

dfs(root->left, result);

dfs(root->right, result);

}

```

#### DFS 深度搜索-从下向上（分治法）

```c++

vector<int> preOrderTraversal(TreeNode *root) {

return divideAndConquer(root);

}

vector<int> divideAndConquer(TreeNode *root) {

vector<int> result;

if (!root) {

return result;

}

// 分治(Divide)

auto left = divideAndConquer(root->left);

auto right = divideAndConquer(root->right);

// 合并结果(Conquer)

result.push_back(root->val);

result.insert(result.end(), left.begin(), left.end());

result.insert(result.end(), right.begin(), right.end());

return result;

}

```

注意点：

> DFS 深度搜索（从上到下） 和分治法区别：前者一般将最终结果通过指针参数传入，后者一般递归返回结果最后合并

#### BFS 层次遍历

```c++

vector<int> levelOrder(TreeNode *root) {

vector<int> result;

if (!root) {

return result;

}

queue<TreeNode *> queue;

queue.push(root);

while (!queue.empty()) {

root = queue.front();

result.push_back(root->val);

if (root->left) {

queue.push(root->left);

}

if (root->right) {

queue.push(root->right);

}

queue.pop();

}

return result;

}

```

### 分治法应用

先分别处理局部，再合并结果

适用场景

- 快速排序

- 归并排序

- 二叉树相关问题

分治法模板

- 递归返回条件

- 分段处理

- 合并结果

```c++

ResultType traversal(TreeNode *root) {

// nil or leaf

if (!root) {

// do something and return

}

// Divide

auto left = traversal(root->left);

auto right = traversal(root->right);

// Conquer

auto result = merge(left, right);

return result;

}

```

#### 典型示例

```c++

vector<int> preOrderTraversal(TreeNode *root) {

return divideAndConquer(root);

}

vector<int> divideAndConquer(TreeNode *root) {

vector<int> result;

if (!root) {

return result;

}

// 分治(Divide)

auto left = divideAndConquer(root->left);

auto right = divideAndConquer(root->right);

// 合并结果(Conquer)

result.push_back(root->val);

result.insert(result.end(), left.begin(), left.end());

result.insert(result.end(), right.begin(), right.end());

return result;

}

```

#### 归并排序  

```c++

template<typename T>

static void MergeSort(T arr[], int len) {

auto tmp = new T[len];

mergeSort(arr, 0, len - 1, tmp);

delete[] tmp;

}

template<typename T>

static void mergeSort(T arr[], int begin, int end, T tmp[]) {

if (begin + 1 >= end) {

return;

}

auto mid = begin + (end - begin) / 2;

auto begin1 = begin;

auto end1 = mid;

auto begin2 = mid + 1;

auto end2 = end;

mergeSort(arr, begin1, end1, tmp);

mergeSort(arr, begin2, end2, tmp);

// merge two parts

auto index = begin;

while (begin1 <= end1 && begin2 <= end2) {

tmp[index++] = arr[begin1] < arr[begin2] ? arr[begin1++] : arr[begin2++];

}

while (begin1 <= end1) {

tmp[index++] = arr[begin1++];

}

while (begin2 <= end2) {

tmp[index++] = arr[begin2++];

}

for (int i = begin; i <= end; ++i) {

arr[i] = tmp[i];

}

}

```

注意点

> 递归需要返回结果用于合并

#### 快速排序  

```c++

template<typename T>

static void QuickSort(T arr[], int len) {

quickSort(arr, 0, len - 1);

}

template<typename T>

static void quickSort(T arr[], int begin, int end) {

if (begin >= end) {

return;

}

auto pivot = partition(arr, begin, end);

quickSort(arr, begin, pivot - 1);

quickSort(arr, pivot + 1, end);

}

template<typename T>

static int partition(T arr[], int begin, int end) {

auto base = arr[end];

auto lessInsert = begin;

for (int i = begin; i < end; ++i) {

if (arr[i] < base) {

swap(arr[lessInsert++], arr[i]);

}

}

swap(arr[lessInsert], arr[end]);

return lessInsert;

}

```

注意点：

> 快排由于是原地交换所以没有合并过程

> 传入的索引是存在的索引（如：0、length-1 等），越界可能导致崩溃

常见题目示例

#### maximum-depth-of-binary-tree

[maximum-depth-of-binary-tree](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/)

> 给定一个二叉树，找出其最大深度。

思路：分治法

```c++

int maxDepth(TreeNode* root) {

if (!root) {

return 0;

}

// divide：分左右子树分别计算

auto leftDepth = maxDepth(root->left);

auto rightDepth = maxDepth(root->right);

// conquer：合并左右子树结果

return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;

}

```

#### balanced-binary-tree

[balanced-binary-tree](https://leetcode-cn.com/problems/balanced-binary-tree/)

> 给定一个二叉树，判断它是否是高度平衡的二叉树。

思路：分治法，左边平衡 && 右边平衡 && 左右两边高度 <= 1，

因为需要返回是否平衡及高度，要么返回两个数据，要么合并两个数据，

所以用-1 表示不平衡，>0 表示树高度（二义性：一个变量有两种含义）。

```c++

bool isBalanced(TreeNode *root) {

return maxDepth(root) != -1;

}

int maxDepth(TreeNode *root) {

if (!root) {

return 0;

}

auto left = maxDepth(root->left);

auto right = maxDepth(root->right);

if (left == -1 || right == -1 || left - right > 1 || right - left > 1) {

return -1;

}

return (left > right ? left : right) + 1;

}

```

注意

> 一般工程中，结果通过两个变量来返回，不建议用一个变量表示两种含义

#### binary-tree-maximum-path-sum

[binary-tree-maximum-path-sum](https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/)

> 给定一个**非空**二叉树，返回其最大路径和。

思路：分治法，分为三种情况：左子树最大路径和最大，右子树最大路径和最大，左右子树最大加根节点最大，需要保存两个变量：一个保存子树最大路径和，一个保存左右加根节点和，然后比较这个两个变量选择最大值即可

```c++

int maxPathSum(TreeNode *root) {

auto maxSum = std::numeric_limits<int>::min();

calcMaxPath(root, maxSum);

return maxSum;

}

int calcMaxPath(TreeNode *&root, int &maxSum) {

if (!root) {

return 0;

}

// 如果左右子树为负，直接丢弃该部分（不需要从一个叶子节点走到另一个叶子）设置为0

auto left = max(calcMaxPath(root->left), 0);

auto right = max(calcMaxPath(root->right), 0);

// 取当前值与当前"闭环"（左右子树+当前节点）的最大值

// 注意，初始值要设置为最小数！

// 子树可以不舍弃负数，但是结果不能（必须至少经过一个节点）

// 当前节点为叶子时，right + left + root->val = 0 + 0 + root->val

maxSum = max(maxSum, left + right + root->val);

// 已经处理过同时涉及左右子树+当前节点的可能

// 对于后续处理，只有一种可能，以当前节点为根的这颗树，取一条路径返回——左右子树最大值 + 当前节点

return max(left, right) + root->val;

}

```

#### lowest-common-ancestor-of-a-binary-tree

[lowest-common-ancestor-of-a-binary-tree](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)

> 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

思路：分治法，有左子树的公共祖先或者有右子树的公共祖先，就返回子树的祖先，否则返回根节点

```c++

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

if (!root) {

return nullptr;

}

// 相等 直接返回root节点即可

if (root == p || root == q) {

return root;

}

// Divide

auto left = lowestCommonAncestor(root->left, p, q);

auto right = lowestCommonAncestor(root->right, p, q);

// Conquer

// 左右两边都不为空，则根节点为祖先

if (left && right) {

return root;

}

return left ? left : right;

}

```

### BFS 层次应用

#### binary-tree-level-order-traversal

[binary-tree-level-order-traversal](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)

> 给你一个二叉树，请你返回其按  **层序遍历**  得到的节点值。 （即逐层地，从左到右访问所有节点）

思路：用一个队列记录一层的元素，然后扫描这一层元素添加下一层元素到队列（一个数进去出来一次，所以复杂度 O(logN)）

```c++

vector<vector<int>> levelOrder(TreeNode* root) {

vector<vector<int>> ret;

if (!root) {

return ret;

}

queue<TreeNode*> queue;

queue.push(root);

while (!queue.empty()) {

vector<int> levelValues;

for (auto levelNodeNum = queue.size(); levelNodeNum > 0; --levelNodeNum) {

auto node = queue.front();

queue.pop();

levelValues.push_back(node->val);

if (node->left) {

queue.push(node->left);

}

if (node->right) {

queue.push(node->right);

}

}

ret.push_back(levelValues);

}

return ret;

}

```

#### binary-tree-level-order-traversal-ii

[binary-tree-level-order-traversal-ii](https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/)

> 给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

思路：在层级遍历的基础上，翻转一下结果即可

```c++

vector<vector<int>> levelOrderBottom(TreeNode *root) {

auto result = levelOrder(root);

reverse(result);

return result;

}

vector<vector<int>> levelOrder(TreeNode *root) {

vector<vector<int>> ret;

if (!root) {

return ret;

}

queue<TreeNode *> queue;

queue.push(root);

while (!queue.empty()) {

vector<int> levelValues;

for (auto levelNodeNum = queue.size(); levelNodeNum > 0; --levelNodeNum) {

auto node = queue.front();

queue.pop();

levelValues.push_back(node->val);

if (node->left) {

queue.push(node->left);

}

if (node->right) {

queue.push(node->right);

}

}

ret.push_back(levelValues);

}

return ret;

}

void reverse(vector<vector<int>> &result) {

for (int i = 0, j = result.size() - 1; i < j; ++i, --j) {

swap(result[i], result[j]);

}

}

```

#### binary-tree-zigzag-level-order-traversal

[binary-tree-zigzag-level-order-traversal](https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/)

> 给定一个二叉树，返回其节点值的锯齿形层次遍历。Z 字形遍历

```c++

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {

vector<vector<int>> ret;

if (!root) {

return ret;

}

queue<TreeNode *> queue;

queue.push(root);

auto l2r = true;

while (!queue.empty()) {

vector<int> levelValues;

for (auto levelNodeNum = queue.size(); levelNodeNum > 0; --levelNodeNum) {

auto node = queue.front();

queue.pop();

levelValues.push_back(node->val);

if (node->left) {

queue.push(node->left);

}

if (node->right) {

queue.push(node->right);

}

}

if (l2r) {

ret.emplace_back(levelValues);

} else {

ret.emplace_back(

levelValues.rbegin(),

levelValues.rend()

);

}

l2r = !l2r;

}

return ret;

}

```

### 二叉搜索树应用

#### validate-binary-search-tree

[validate-binary-search-tree](https://leetcode-cn.com/problems/validate-binary-search-tree/)

> 给定一个二叉树，判断其是否是一个有效的二叉搜索树。

思路 1：中序遍历，检查结果列表是否已经有序

思路 2：分治法，判断左 MAX < 根 < 右 MIN

```c++

bool isValidBST(TreeNode *root) {

if (!root) {

return true;

}

// 思路 1：中序遍历，检查结果列表是否已经有序

auto inOrderValues = vector<int>();

inOrder(root, inOrderValues);

for (auto iter = inOrderValues.cbegin() + 1; iter != inOrderValues.cend(); ++iter) {

if (*(iter - 1) >= *iter) {

return false;

}

}

return true;

}

void inOrder(TreeNode *root, vector<int> &values) {

if (!root) {

return;

}

inOrder(root->left, values);

values.push_back(root->val);

inOrder(root->right, values);

}

```

```c++

struct Result {

TreeNode *maxNode;

TreeNode *minNode;

bool isValidate;

Result(bool validate = true, TreeNode *max = nullptr, TreeNode *min = nullptr)

: isValidate(validate), maxNode(max), minNode(min) {

}

};

bool isValidBST(TreeNode *root) {

if (!root) {

return true;

}

return helper(root).isValidate;

}

Result helper(TreeNode *root) {

if (!root) {

return {};

}

auto left = helper(root->left);

auto right = helper(root->right);

if (!(left.isValidate && right.isValidate)) {

return {false};

}

if (left.maxNode && left.maxNode->val >= root->val) {

return {false};

}

if (right.minNode && right.minNode->val <= root->val) {

return {false};

}

return {

true,

right.maxNode ? right.maxNode : root,

left.minNode ? left.minNode : root,

};

}

```

#### insert-into-a-binary-search-tree

[insert-into-a-binary-search-tree](https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/)

> 给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。

思路：找到最后一个叶子节点满足插入条件即可

```c++

TreeNode* insertIntoBST(TreeNode* root, int val) {

if (!root) {

root = new TreeNode(val);

return root;

}

if (root->val > val) {

root->left = insertIntoBST(root->left, val);

} else {

root->right = insertIntoBST(root->right, val);

}

return root;

}

```

## 总结

- 掌握二叉树递归与非递归遍历

- 理解 DFS 前序遍历与分治法

- 理解 BFS 层次遍历

## 练习

- [ ] [maximum-depth-of-binary-tree](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/)

- [ ] [balanced-binary-tree](https://leetcode-cn.com/problems/balanced-binary-tree/)

- [ ] [binary-tree-maximum-path-sum](https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/)

- [ ] [lowest-common-ancestor-of-a-binary-tree](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)

- [ ] [binary-tree-level-order-traversal](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)

- [ ] [binary-tree-level-order-traversal-ii](https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/)

- [ ] [binary-tree-zigzag-level-order-traversal](https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/)

- [ ] [validate-binary-search-tree](https://leetcode-cn.com/problems/validate-binary-search-tree/)

- [ ] [insert-into-a-binary-search-tree](https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/)