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

【二叉树算法大盘点】其实，二叉树的先序遍历，中序遍历，后序遍历，都是深度优先搜索，深搜是一种思想，并不具体指代实现方式，你可以使用递归，也可以使用栈来实现，所以上面提到的都是深度优先搜索的实现方式，毕竟“深度优先”嘛。
那在这里我就是提几个实际的应用的例子，加深一下印象。
二叉树的最大深度
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.left=root.right;root.right=temp;}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<Integer> list = new ArrayList<Integer>;private ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>;public ArrayList<ArrayList<Integer>> 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<Integer>(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;i<=endin;i++){if(in[i] == pre[startpre]){root.left = reConstructBinaryTree(pre,startpre+1,startpre+i-startin,in,startin,i-1);root.right = reConstructBinaryTree(pre,startpre+i-startin+1,endpre,in,i+1,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<TreeNode> queue = new LinkedList<>;queue.add(root);while (!queue.isEmpty) {TreeNode node = queue.remove;if (node != ) {res.Append(node.val).append(",");queue.add(node.left);queue.add(node.right);} else {res.append(",");}}return res.toString;}反序列化：public TreeNode deserialize(String data) {if (data =https://www.isolves.com/it/cxkf/sf/2020-06-19/= || data.length == 0) {return ;}String dataArr = data.split(",");// 层次遍历逆向还原二叉树int index = 0;TreeNode root = toNode(dataArr[index]);LinkedList queue = new LinkedList<>;queue.add(root);while (index < dataArr.length - 2 && !queue.isEmpty) {TreeNode cur = queue.remove;// 添加左子节点TreeNode leftNode = toNode(dataArr[++index]);cur.left = leftNode;// 队列中的节点用于为其赋值孩子节点，若该节点本身为，// 没有孩子节点，便不再添加到队列中，下同理if (leftNode != ) {queue.add(leftNode);}// 添加右子节点TreeNode rightNode = toNode(dataArr[++index]);cur.right = rightNode;if (rightNode != ) {queue.add(rightNode);}}return root;}private TreeNode toNode(String val) {if (!"".equals(val)) {return new TreeNode(Integer.parseInt(val));} else {return ;}}

文章插图
广度优先搜索（BFS）

首先将根节点放入队列中。
从队列中取出第一个节点，并检验它是否为目标。
如果找到目标，则结束搜索并回传结果。
否则将它所有尚未检验过的直接子节点加入队列中。
若队列为空，表示整张图都检查过了——亦即图中没有欲搜索的目标。结束搜索并回传“找不到目标” 。
重复步骤2 。

public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<List<Integer>>;List<TreeNode> quene = new ArrayList<TreeNode>;if(root == ){return res;}quene.add(root);while(quene.size!=0){int count = quene.size;List<Integer> list = new ArrayList<Integer>;while(count>0){TreeNode temp =quene.remove(0);list.add(temp.val);if(temp.left!=){quene.add(temp.left);}if(temp.right!=){quene.add(temp.right);}count--;}res.add(list);}return res;}