二叉树算法大盘点 _二叉树算法

文章插图
作者 | BoCong-Deng
题图 | 视觉中国
出品 | CSDN博客
树结构对于程序员来说应该不陌生，特别是二叉树，基本只要接触算法这一类的都一定会碰到的，所以我打算通过一篇文章，对二叉树结构的相关算法进行总结汇总，思路和代码实现相结合，让你不在惧怕二叉树。（ps：后面我还想写一篇树结构的高级篇，就是多叉数，就是对我平时看算法论文碰到的一些新奇的算法，比如B树、B+树，还有我一种叫做Bed树的新奇算法等等）
单纯就是想分享技术博文，还想说一句就是，如果觉得有用，请点个关注、给个赞吧，也算对我来说是个宽慰，毕竟也得掉不少头发，嘿嘿嘿。
下面的思路讲解中，我会给出一个类伪代码的思路，然后进行相关说明，也就是一种思路框架，有了思路框架，以后碰到问题就直接交给框架完成。本文主要说一下二叉搜索树（Binary Search Tree，简称 BST），BST是一种很常用的的二叉树。它的定义是：一个二叉树中，任意节点的值要大于等于左子树所有节点的值，且要小于等于右边子树的所有节点的值。如下就是一个符合定义的 BST：

文章插图
后面如果遇到特殊的思路结构，如多叉树，我会特别说明。首先我们先给出二叉树的节点定义（这个定义应该不陌生吧，有刷算法题都会碰到）。
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}

文章插图
递归
不过这里要说明一点的是，在伪代码中的“进行想要的操作”的位置，不一定就在我放置的位置，具体位置还需要我们根据不同的实际需求进行判断。不过因为前中后序的遍历，递归进入的时机应该需要和我的一样。
先序遍历
遍历根节点，如果根节点为空，返回；否则，遍历根节点，然后先序遍历左子树，再先序遍历右子树。
public void preorderTraverse(TreeNode root){System.out.print(node.val+" ");preorderTraverse(root.left);preorderTraverse(root.right);}中序遍历
路过根节点，如果根节点为空，返回；否则，中序遍历左子树，然后遍历根节点，再中序遍历右子树。
public void inorderTraverse(TreeNode root){inorderTraverse(root.left);System.out.print(node.val+" ");inorderTraverse(root.right);}后序遍历
路过根节点，如果根节点为空，返回；否则，后序遍历左子树，再后序遍历右子树，最后遍历根节点。
public void postorderTraverse(TreeNode root){postorderTraverse(root.left);postorderTraverse(root.right);System.out.print(node.val+" ");}

文章插图
迭代（非递归）
我们使用迭代的思想，其实就是利用循环和栈来模拟递归的操作，上面递归的操作，其实就是一个不断将自己以及左右子节点进行压栈和出栈的过程，如果理解了上面的算法下面的算法就好理解了
前序遍历
public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>;if(root==){return list;}Stack<TreeNode> stack = new Stack<>;stack.push(root);while(!stack.isEmpty){TreeNode res = stack.pop;if(res.right != )stack.push(res.right);if(res.left != )stack.push(res.left);list.add(res.val);}return list;}中序遍历
public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>;if(root==){return list;}Stack<TreeNode> stack = new Stack<>;TreeNode curr = root;while(curr != || !(stack.isEmpty)){if(curr!= ){stack.push(curr);curr = curr.left;}else{curr = stack.pop;list.add(curr.val);curr = curr.right;}}return list;}后序遍历
我们可以很简单的实现另一种遍历：”根->右->左“遍历。虽然这种遍历没有名字，但是他是后序遍历的反序。所以我们可以利用两个栈，利用栈的LIFO特点，来实现后续遍历。
public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>;if(root==){return list;}Stack<TreeNode> stack = new Stack<>;stack.push(root);while(!stack.isEmpty){TreeNode res = stack.pop;if(res.left != )stack.push(res.left);if(res.right != )stack.push(res.right);list.add(res.val);}list.reserve;return list;}