个人网站设计与制作代码,可以在线观看的免费资源,怎么做网站黑链,宝塔wordpress打开卡顿二叉树和递归
0 LeetCode297 二叉树的序列化和反序列化
序列化是将一个数据结构或者对象转换为连续的比特位的操作#xff0c;进而可以将转换后的数据存储在一个文件或者内存中#xff0c;同时也可以通过网络传输到另一个计算机环境#xff0c;采取相反方式重构得到原数据…二叉树和递归
0 LeetCode297 二叉树的序列化和反序列化
序列化是将一个数据结构或者对象转换为连续的比特位的操作进而可以将转换后的数据存储在一个文件或者内存中同时也可以通过网络传输到另一个计算机环境采取相反方式重构得到原数据。请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。示例: 你可以将以下二叉树1/ \2 3/ \4 5序列化为 [1,2,3,null,null,4,5]
提示: 这与 LeetCode 目前使用的方式一致详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式你也可以采用其他的方法解决这个问题。说明: 不要使用类的成员 / 全局 / 静态变量来存储状态你的序列化和反序列化算法应该是无状态的。import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;public class Codec {// Encodes a tree to a single string.public String serialize(TreeNode root) {if (root null) {return [];}QueueString res new LinkedList();QueueTreeNode queue new LinkedList();queue.offer(root);res.offer(String.valueOf(root.val));while(!queue.isEmpty()) {TreeNode node queue.poll();// 有左节点就插入左节点没有就插入nullif (node.left ! null) {queue.offer(node.left);res.offer(String.valueOf(node.left.val));} else {res.offer(null);}// 有右节点就插入右节点没有就插入nullif (node.right ! null) {queue.offer(node.right);res.offer(String.valueOf(node.right.val));} else {res.offer(null);}}StringBuilder sb new StringBuilder();sb.append([);while(!res.isEmpty()) {sb.append(res.poll());if (!res.isEmpty()) {sb.append(,);}}sb.append(]);return sb.toString();}// Decodes your encoded data to tree.public TreeNode deserialize(String data) {data data.substring(1, data.length()-1);if (data.length() 0) {return null;}QueueString ls new LinkedList(Arrays.asList(data.split(,)));QueueTreeNode queue new LinkedList();TreeNode root null;while(!ls.isEmpty()) {String res ls.poll();// 创建根节点if (root null) {root new TreeNode(Integer.parseInt(res));queue.offer(root);continue;}// 注意ls的长度总是奇数的所以除了根节点其余节点创建时可以一次取两个ls中的元素TreeNode father queue.poll();// 创建左节点if (!null.equals(res)) {TreeNode curr new TreeNode(Integer.parseInt(res));assert father ! null;father.left curr;queue.offer(curr);}// 创建右节点res ls.poll();assert res ! null;if (!null.equals(res)) {TreeNode curr new TreeNode(Integer.parseInt(res));assert father ! null;father.right curr;queue.offer(curr);}}return root;}
}1 二叉树的天然递归结构
递归的组成部分
递归终止条件递归过程(也称递归具体逻辑)
Leetcode104.Maximum Depth of Binary Tree 求二叉树的最大深度
给定一个二叉树找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。示例
给定二叉树 [3,9,20,null,null,15,7]3/ \9 20/ \15 7public int maxDepth(TreeNode root) {// 递归的退出条件if (root null) {// 当前树的根节点为null,那么当前树的深度为0return 0;}// 递归计算左子树最大深度int lMax maxDepth(root.left);// 递归计算右子树最大深度int rMax maxDepth(root.right);// 找到左右子树深度较大地那个加1是因为当前层在递归回退时也算一层return Math.max(lMax, rMax) 1;
}111.二叉树的最小深度
class Solution {public int minDepth(TreeNode root) {if(root null){return 0;}if(root.left null || root.right null){return Math.max(minDepth(root.left), minDepth(root.right)) 1;}return Math.min(minDepth(root.left), minDepth(root.right)) 1;}
}上面的代码中的max实际是考虑了左右子树为空的情况是下面代码的简化
lass Solution {public int minDepth(TreeNode root) {if (root null)return 0;if (root.left null root.right null)return 1;if (root.left ! null root.right null)return minDepth(root.left) 1;if (root.right ! null root.left null)return minDepth(root.right) 1;return Math.min(minDepth(root.left) , minDepth(root.right)) 1;}
}2 Leetcode226号问题反转二叉树
输入4/ \2 7/ \ / \
1 3 6 9
输出4/ \7 2/ \ / \
9 6 3 1/************************************************************ Description : 反转二叉树* 输入** 4* / \* 2 7* / \ / \* 1 3 6 9* 输出** 4* / \* 7 2* / \ / \* 9 6 3 1** author : 梁山广(Liang Shan Guang)* date : 2019/8/22 07:55* email : liangshanguang2gmail.com***********************************************************/
package Chapter07BSTAndRecursion.InverseBinaryTree;class Solution {public TreeNode invertTree(TreeNode root) {if(root null){return null;}// 不为空的最下面的一个节点交换左右子树即可TreeNode right invertTree(root.right);TreeNode left invertTree(root.left);// 下面是交换的核心root.right left;root.left right;return root;}
}类似的问题100、101、222、110
100. 相同的树
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if(p null q null) {return true;}if(p null || q null) {return false;}if(p.val ! q.val){// 当前节点不相等直接返回falsereturn false;}else {// 相等地话直接往下递归return isSameTree(p.left, q.left) isSameTree(p.right, q.right);}}
}101.对称二叉树 和上面的第100题思路是完全一致的 class Solution {public boolean isSymmetric(TreeNode root) {if(root null) {return true;}return isSymmetric(root.left, root.right);}// 利用上一节判断两棵树是否是相同树的代码来判断两个树是否堆成private boolean isSymmetric(TreeNode p, TreeNode q) {if(p null q null){return true;}if(p null || q null){return false;}if(p.val ! q.val){return false;}return isSymmetric(p.left, q.right) isSymmetric(p.right, q.left);}
}222.完全二叉树的节点个数 题目也太简单了吧还好意思说是中级 class Solution {public int countNodes(TreeNode root) {if(root null){return 0;}return countNodes(root.left) countNodes(root.right) 1;}
}110.平衡二叉树
// 递归解决计算子树高度-1表示子树已经不平衡了
class Solution {public boolean isBalanced(TreeNode root) {// 计算各个点的深度 -1代表不平衡了return calDepth(root) ! -1;}// 计算子树高度-1表示已经不平衡了private int calDepth(TreeNode node){if(node null){return 0;}// 递归计算左子树最大深度int lMax calDepth(node.left);// 递归计算右子树最大深度int rMax calDepth(node.right);// 左右子树高度差大于1时当前子树的高度返回-1if(lMax 0 rMax 0 Math.abs(lMax - rMax) 1){return Math.max(lMax, rMax) 1;}else {return -1;}}
}3 注意递归的终止条件
LeetCode112.路径总和
给定一个二叉树和一个目标和判断该树中是否存在根节点到叶子节点的路径这条路径上所有节点值相加等于目标和。说明: 叶子节点是指没有子节点的节点。示例:
给定如下二叉树以及目标和 sum 225/ \4 8/ / \11 13 4/ \ \7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5-4-11-2class Solution {// 不要用sum 0作为递归终止条件容易因为一开始传入地就是0而因为异常public boolean hasPathSum(TreeNode root, int sum) {// 1.递归终止条件if (root null) {return false;}if (root.left null root.right null) {// 注意题目中有说路径终点必须是叶子节点return root.val sum;}// 2.递归的具体逻辑// 总和减去当前节点的值然后看当前节点是否存在子树的节点和等于前面的新sumif (hasPathSum(root.left, sum - root.val)) {return true;}if (hasPathSum(root.right, sum - root.val)) {return true;}// 两侧都没找到返回falsereturn false;}
}404.左叶子之和 用一个布尔变量标记是不是左子树 class Solution {public int sumOfLeftLeaves(TreeNode root) {// 递归具体逻辑return sumOfLeftLeaves(root, false);}private int sumOfLeftLeaves(TreeNode node, boolean isLeft) {// 1.递归退出条件if (node null) {return 0;}// 左右子树都为空表明是叶子节点if (node.left null node.right null) {// 是左子节点才返回节点的值if (isLeft) {return node.val;} else {// 右子节点就返回0,不影响最终的和return 0;}}// 2.递归具体逻辑return sumOfLeftLeaves(node.left, true) sumOfLeftLeaves(node.right, false);}
}4 定义递归问题
257.二叉树的所有路径
给定一个二叉树返回所有从根节点到叶子节点的路径。说明: 叶子节点是指没有子节点的节点。示例:输入:1/ \
2 3\5输出: [1-2-5, 1-3]解释: 所有根节点到叶子节点的路径为: 1-2-5, 1-3class Solution {public ListString binaryTreePaths(TreeNode root) {ListString result new ArrayList();if (root null) {return result;}if (root.left null root.right null) {result.add(String.valueOf(root.val));}// 获取并拼接左子树字符串ListString listL binaryTreePaths(root.left);for (int i 0; i listL.size(); i) {result.add(root.val - listL.get(i));}// 获取并拼接右子树字符串ListString listR binaryTreePaths(root.right);for (int i 0; i listR.size(); i) {result.add(root.val - listR.get(i));}return result;}
}113.路径总和 II
/************************************************************ Description : 113.路径总和* author : 梁山广(Liang Shan Guang)* date : 2020/1/22 10:59* email : liangshanguang2gmail.com***********************************************************/
package Chapter07BSTAndRecursion.LeetCode113路径总和2;import Chapter07BSTAndRecursion.BSTUtil;
import Chapter07BSTAndRecursion.TreeNode;import java.util.ArrayList;
import java.util.List;class Solution {public ListListInteger pathSum(TreeNode root, int sum) {ListListInteger pathList new ArrayList();ListInteger path new ArrayList();pathSum(root, sum, path, pathList);return pathList;}public void pathSum(TreeNode node, int sum, ListInteger path, ListListInteger pathList) {if (node null) {return;}// 当前节点path.add(node.val);// 左右子树都为空说明到了叶子节点把当前路径加到路径列表中if (node.left null node.right null) {if (node.val sum) {// 必须从path中新建一个来存储当前路径否则后续修改path会会影响pathList.add(new ArrayList(path));}}pathSum(node.left, sum - node.val, path, pathList);pathSum(node.right, sum - node.val, path, pathList);// 当前层的递归退出时要删除当前节点path.remove(path.size() - 1);}/*** [5,4,8,11,null,13,4,7,2,null,null,5,1]* 22* p* [-2,null,-3]* -5*/public static void main(String[] args) {Integer[] arr {1, -2, -3, 1, 3, -2, null, -1};int sum 2;TreeNode root BSTUtil.convert(arr);System.out.println(new Solution().pathSum(root, sum));}
}129.求根到叶子节点数字之和 和上面的113类似而且还简单点不用筛选路径了 class Solution {public int sumNumbers(TreeNode root) {ListListInteger pathList new ArrayList();ListInteger path new ArrayList();pathSum(root, path, pathList);int sum 0;for (ListInteger pathTmp : pathList) {int num 0;for (Integer numSingle : pathTmp) {num num * 10 numSingle;}sum num;}return sum;}public void pathSum(TreeNode node, ListInteger path, ListListInteger pathList) {if (node null) {return;}// 当前节点path.add(node.val);// 左右子树都为空说明到了叶子节点把当前路径加到路径列表中if (node.left null node.right null) {// 必须从path中新建一个来存储当前路径否则后续修改path会会影响pathList.add(new ArrayList(path));}pathSum(node.left, path, pathList);pathSum(node.right, path, pathList);// 当前层的递归退出时要删除当前节点path.remove(path.size() - 1);}
}5 稍微复杂的递归逻辑
437.Path Sum III 双层递归首先先序递归遍历每个节点再以每个节点作为起始点递归寻找满足条件的路径。 // 递归遍历每个节点每个节点作为根节点进行一次113.Path Sum II的操作
class Solution {// 符合条件的路径总数int cnt 0;public int pathSum(TreeNode root, int sum) {if(root null){return cnt;}// Todo:对当前节点进行Path Sum IIpathSumII(root, sum);pathSum(root.left, sum);pathSum(root.right, sum);return cnt;}private void pathSumII(TreeNode node, int sum){if(node null){return;}int newSum sum - node.val;if(newSum 0){cnt;}pathSumII(node.left, newSum);pathSumII(node.right, newSum);}
}6 二分搜索树的问题
235.二叉搜索树的最近公共祖先
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root null){return null;}// pq均在右子树if(p.val root.val q.val root.val){return lowestCommonAncestor(root.right, p, q);}// pq均在左子树if(p.val root.val q.val root.val){return lowestCommonAncestor(root.left, p, q);}// p和q在root的两侧当前的root肯定是最近的父节点return root;}
}98.验证二叉树是否是二分搜索树
class Solution {/*** 中序遍历以node作为根节点的二分搜索树*/private void inOrder(TreeNode node, ListInteger list) {// 递归终止条件if (node null) {// 遍历到null节点就返回上一层递归return;}// 递归组成逻辑// 2.遍历左子树inOrder(node.left, list);// 1.访问当前节点。需要存储时可以放到list中list.add(node.val);// 3.遍历右子树inOrder(node.right, list);}// 中序遍历的结果是有序地则说明二叉树是一个二叉搜索树public boolean isValidBST(TreeNode root) {ListInteger list new ArrayList();inOrder(root, list);for(int i 1; i list.size(); i){if(list.get(i) list.get(i - 1)){return false;}}return true;}
}450.删除二叉搜索树中的节点 参考地Part2Basic/Chapter06BST/BST.java class Solution {public TreeNode deleteNode(TreeNode root, int key) {return remove(root, key);}/*** 寻找以node作为跟节点的二分搜索树的最小节点** param node 根节点*/private TreeNode minimum(TreeNode node) {if (node.left null) {return node;}return minimum(node.left);}/*** 删除以node作为根节点的二分搜索树中的最小节点并返回删除节点后的新的二分搜索树的根节点** param node 根节点*/private TreeNode removeMin(TreeNode node) {// 递归终止条件if (node.left null) {// 递归遍历到左子树为空说明找到了最小节点node// node.right是否为空都可以正常返回给上一级的父节点来设置父节点的左节点直接指向当前节点的右子树TreeNode rightNode node.right;node.right null;return rightNode;}// 递归组成逻辑// 当左节点不是null时就正常往下递归返回当前节点给上一层节点设置下自己的左节点node.left removeMin(node.left);return node;}/*** 删除** param node 二分搜索树的根节点* param e 待删除节点的值* return 要挂载到当前节点父节点的子树*/private TreeNode remove(TreeNode node, int e) {// 递归终止条件if (node null) {return null;}// 递归组成逻辑// 还没找到就接着往下找if (e node.val) {// 要找的值比当前节点小向左递归node.left remove(node.left, e);return node;} else if (e node.val) {// 要找的值比当前节点大向右递归node.right remove(node.right, e);return node;} else {// node.e e 找到相等的节点了下面删除指定值的节点if (node.left null) {TreeNode rightNode node.right;// 释放引用node.right null;// 左节点为空把node的右子树挂接到node的父亲节点即可return rightNode;}if (node.right null) {TreeNode leftNode node.left;// 释放引用node.left null;// 右节点为空把node的左子树挂接到node的父亲节点即可return leftNode;}// node的左右子树都不为空就找node的右子树的最小值来代替nodeTreeNode minimumRight minimum(node.right);// 警告下面两行代码一定不要颠倒一定要先设置right再设置left否则会出现迭代引用因为下面那行改变了node.right的结构。参考问题:https://coding.imooc.com/learn/questiondetail/143936.html// 选出node右子树最小元素来代替node那么右子树最小元素就要从原来位置删掉minimumRight.right removeMin(node.right);// 替换当前节点node的左右子树minimumRight.left node.left;// 释放node的引用node.left node.right null;// 返回给上一级来设置父节点return minimumRight;}}
}108.将有序数组转换为二叉搜索树
class Solution {// 升序数组是中序遍历的结果答案是层序遍历的结果public TreeNode sortedArrayToBST(int[] nums) {return buildTree(nums, 0, nums.length - 1);}// 左右等分建立左右子树中间节点作为子树根节点递归该过程private TreeNode buildTree(int[] nums, int l, int r){if(l r){return null;}// 等效于mid (l r) / 2下面的实现是为了防止整型溢出int mid l (r - l) /2;TreeNode root new TreeNode(nums[mid]);root.left buildTree(nums, l, mid - 1);root.right buildTree(nums, mid 1, r);return root;}
}230.二叉搜索树中第K小的元素
class Solution {int i 0;int kth 0;int kthSmallestVal 0;public int kthSmallest(TreeNode root, int k) {kth k;inOrder(root);return kthSmallestVal;}// 中序遍历的结果是升序排列的所以找到第k小的元素就是累计中序遍历到额递归层数private void inOrder(TreeNode node){if(node null){return;}inOrder(node.left);i;if(i kth){kthSmallestVal node.val;}inOrder(node.right);}
}236. 二叉树的最近公共祖先 参考235号问题 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// LCA 问题if (root null) {return root;}if (root p || root q) {return root;}TreeNode left lowestCommonAncestor(root.left, p, q);TreeNode right lowestCommonAncestor(root.right, p, q);if (left ! null right ! null) {return root;} else if (left ! null) {return left;} else if (right ! null) {return right;}return null;}
}
