怎样做58网站,网页版小游戏在线玩,Linux主机设置网站首页,如何创建博客网站作者 | BoCong-Deng题图 | 视觉中国出品 | CSDN博客树结构对于程序员来说应该不陌生#xff0c;特别是二叉树#xff0c;基本只要接触算法这一类的都一定会碰到的#xff0c;所以我打算通过一篇文章#xff0c;对二叉树结构的相关算法进行总结汇总#xff0c;思路和代码实…作者 | 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 preorderTraversal(TreeNode root) {List list new ArrayList;if(root){return list;}Stack 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 inorderTraversal(TreeNode root) {List list new ArrayList;if(root){return list;}Stack 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 preorderTraversal(TreeNode root) {List list new ArrayList;if(root){return list;}Stack 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;}深度优先搜索(DFS)其实二叉树的先序遍历中序遍历后序遍历都是深度优先搜索深搜是一种思想并不具体指代实现方式你可以使用递归也可以使用栈来实现所以上面提到的都是深度优先搜索的实现方式毕竟“深度优先”嘛。那在这里我就是提几个实际的应用的例子加深一下印象。二叉树的最大深度public int maxDepth(TreeNode root) {if(root){return 0;}int left maxDepth(root.left);int right maxDepth(root.right);return Math.max(left,right)1;}二叉树的镜像public void Mirror(TreeNode root) {if(root!){if(root.left! || root.right! ){TreeNode temp root.left;root.leftroot.right;root.righttemp;}Mirror(root.left);Mirror(root.right);}}对称二叉树boolean isSymmetrical(TreeNode pRoot){if(pRoot )return true;return real(pRoot.left,pRoot.right);}public boolean real(TreeNode root1,TreeNode root2){if(root1 root2 ){return true;}if(root1 || root2 ){return false;}if(root1.val ! root2.val){return false;}return real(root1.left,root2.right)real(root1.right,root2.left);}路径总和public class Solution {private ArrayList list new ArrayList;private ArrayList listAll new ArrayList;public ArrayList FindPath(TreeNode root,int target) {if(root )return listAll;list.add(root.val);target - root.val;if(target 0 root.left root.right ){listAll.add(new ArrayList(list));}FindPath(root.left,target);FindPath(root.right,target);list.remove(list.size-1);return listAll;}}重建二叉树public TreeNode reConstructBinaryTree(int [] pre,int [] in) {return reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);}public TreeNode reConstructBinaryTree(int [] pre,int startpre,int endpre,int [] in,int startin,int endin){if(startpre endpre || startin endin){return ;}TreeNode root new TreeNode(pre[startpre]);for(int i startin;iendin;i){if(in[i] pre[startpre]){root.left reConstructBinaryTree(pre,startpre1,startprei-startin,in,startin,i-1);root.right reConstructBinaryTree(pre,startprei-startin1,endpre,in,i1,endin);}}return root;}二叉搜索树的最近公共祖先class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root || root p || root q){return root;}TreeNode left lowestCommonAncestor(root.left,p,q);TreeNode right lowestCommonAncestor(root.right,p,q);if(left! right!){return root;}return left!?left:right;}}二叉树的序列化和反序列化序列化public String serialize(TreeNode root) {if (root ) {return ;}// 利用二叉树的层次遍历方式进行序列化StringBuilder res new StringBuilder;LinkedList queue new LinkedList;queue.add(root);while (!queue.isEmpty) {TreeNode node queue.remove;if (node ! ) {res.append(node.val).append(
