二叉树经典算法总结 二叉树和经典算法的关系
实际上，快速排序就是个二叉树的前序遍历java二叉树遍历算法，归并排序就是个二叉树的后序遍历。下面详细说明。
快速排序的逻辑是，若要对 nums[lo..hi] 进行排序，我们先找一个分界点 p，通过交换元素使得 nums[lo..p-1] 都小于等于 nums[p]，且 nums[p+1..hi] 都大于 nums[p]，然后递归地去 nums[lo..p-1] 和 nums[p+1..hi] 中寻找新的分界点，最后整个数组就被排序了。
代码框架
void sort(int[] nums, int lo, int hi) {
/****** 前序遍历位置 ******/
// 通过交换元素构建分界点 p
int p = partition(nums, lo, hi);
/************************/
sort(nums, lo, p - 1);
sort(nums, p + 1, hi);
}
不难发现，这个分界点p就像二叉树中的根节点。
再说说归并排序的逻辑，若要对 nums[lo..hi] 进行排序，我们先对 nums[lo..mid] 排序java二叉树遍历算法-二叉树经典算法总结，再对 nums[mid+1..hi] 排序，最后把这两个有序的子数组合并，整个数组就排好序了。
代码框架
void sort(int[] nums, int lo, int hi) {
int mid = (lo + hi) / 2;
sort(nums, lo, mid);
sort(nums, mid + 1, hi);
/****** 后序遍历位置 ******/
// 合并两个排好序的子数组
merge(nums, lo, mid, hi);
/************************/
}
先把左右节点分别排序最后进行一个整合，实际上就是二叉树的后序遍历，并且和分治算法相应证。
总结：二叉树的算法本质就是递归，合理利用递归即可解决问题。
经典算法题 翻转二叉树
解题思路
通过题目实际上很容易发现这里的翻转就是指左右子节点对称位置进行交换即可。那我们先考虑base case，即根节点左右子节点利用临时节点交换，后面递归实现即可。
代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
// 判断二叉树为空
if (root == null) {
return null;
}
// base case
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
// 递归子节点
invertTree(root.left);
invertTree(root.right);
return root;
}
}
填充每个节点的下一个右侧节点指针 解题思路
本题需要实现类似层级遍历，使得除了每层最右边节点，剩下的节点都指向右边相邻节点。如果只是简单递归链接左右子节点，只能在左右子树分别实现而不能使得左右子树有关联，所以需要单独对左右子树的右节点和左节点进行链接。
代码实现
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
if (root == null) {
return null;
}
connectTwoNode(root.left, root.right);
return root;
}
public void connectTwoNode(Node node1, Node node2) {
if (node1 == null || node2 == null) {
return;
}
// 交换节点算法
node1.next = node2;
// 递归同一父节点下的左右节点
connectTwoNode(node1.left, node1.right);
connectTwoNode(node2.left, node2.right);
// 交换相邻节点，这样就可以覆盖所有层所有节点
connectTwoNode(node1.right, node2.left);
}
}
二叉树展开为链表
解题思路
本题需要解决的问题是将二叉树进行展开并按照先序遍历的顺序展示在根节点的右子树。问题细化，实际上就是将二叉树的左右子树分别展开，然后现将左子树连接到根节点的右孩子；把原来的右子树拼接到左子树末端。伪代码如下：
代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public void flatten(TreeNode root) {
// base case
if (root == null) {
return;
}
// 根据函数定义细分问题，分别处理左右子树
flatten(root.left);
flatten(root.right);
// 后序遍历处理子树
TreeNode left = root.left;
TreeNode right = root.right;
root.left = null;
root.right = left;
// 将原先的右子树接到当前右子树的末端
TreeNode p = root;
// 遍历找到当前右子树最后一个节点
while (p.right != null) {
p = p.right;
}
// 拼接上原来已经展开的右子树到现在的右子树末端
p.right = right;
}
}
最大二叉树
解题思路
根据题意可以知道我们需要不断找出除掉本层root外的最大值，然后通过函数定义分别将数组左右两部分做一个最大二叉树操作即可，当然需要中间分隔的索引。具体代码如下：
代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return build(nums, 0, nums.length - 1);
}
public TreeNode build (int[] nums, int lo, int hi) {
// base case
if (nums == null) {
return null;
}
int max = Integer.MIN_VALUE;
int index = -1;
// 找到当前数组中最大值和其对应索引值
for (int i = lo; i min.val */
boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
// base case
if (root == null) return true;
// 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST
if (min != null && root.val = max.val) return false;
// 限定左子树的最大值是 root.val，右子树的最小值是 root.val
return isValidBST(root.left, min, root)
&& isValidBST(root.right, root, max);
}
在BST中搜索一个数
思路很简单，首先就是遍历实现查找。
代码实现
boolean isInBST(TreeNode root, int target) {
if (root == null) return false;
if (root.val == target) return true;
// 当前节点没找到就递归地去左右子树寻找
return isInBST(root.left, target)
|| isInBST(root.right, target);
}
但是这样似乎对于所有二叉树都适用，没有利用BST的特性。BST是符合左小右大的。那么其实可以联想到二分查找。同理可以优化代码。
boolean isInBST(TreeNode root, int target) {
if (root == null) return false;
if (root.val == target)
return true;
if (root.val target)
return isInBST(root.left, target);
// root 该做的事做完了，顺带把框架也完成了，妙
}
由此可以总结出BST的遍历框架。这个框架对于BST非常实用，建议熟练掌握。代码如下：
void BST(TreeNode root, int target) {
if (root.val == target)
// 找到目标，做点什么
if (root.val target)
BST(root.left, target);
}
在BST中插入一个数
对于在BST中插入元素或者说所有数据结构中插入元素，只有两个步骤，先找到插入位置再进行插入。而上面的遍历框架就给我们提供查找位置的便利。直接利用即可。思路非常清晰简单。
代码实现
TreeNode insertIntoBST(TreeNode root, int val) {
// 找到空位置插入新节点
if (root == null) return new TreeNode(val);
// 判断val的位置
if (root.val val)
root.left = insertIntoBST(root.left, val);
return root;
}
在 BST 中删除一个数
删除情况比较多，需要分类讨论，具体见代码。
<p><pre>TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (root.val == key) {
// 这两个 if 把情况 1 和 2 都正确处理了，情况1即没有子节点，2即有一个子节点
if (root.left == null) return root.right;
if (root.right == null) return root.left;
// 处理情况 3,即被删除的节点有两个子节点
TreeNode minNode = getMin(root.right);
root.val = minNode.val;
root.right = deleteNode(root.right, minNode.val);
} else if (root.val > key) {
root.left = deleteNode(root.left, key);
} else if (root.val root.val) {
root.right = insertIntoBST(root.right, val);
}
if (val key) {
root.left = deleteNode(root.left, key);
} else if (root.val hi) return 1;
int res = 0;
for (int i = lo; i hi) return 1;
// 查备忘录
if (memo[lo][hi] != 0) {
return memo[lo][hi];
}
int res = 0;
for (int i = lo; i hi) {
res.add(null);
return res;
}
// 1、穷举 root 节点的所有可能。
for (int i = lo; i left[2] && root.val left[2] && root.val