如果自己制作网站,网站维护一般要几天,网络架构扁平化,有关网站建设合同Hi~#xff01;这里是奋斗的明志#xff0c;很荣幸您能阅读我的文章#xff0c;诚请评论指点#xff0c;欢迎欢迎 ~~ #x1f331;#x1f331;个人主页#xff1a;奋斗的明志 #x1f331;#x1f331;所属专栏#xff1a;数据结构 #x1f4da;本系列文章为个人学… Hi~这里是奋斗的明志很荣幸您能阅读我的文章诚请评论指点欢迎欢迎 ~~ 个人主页奋斗的明志 所属专栏数据结构 本系列文章为个人学习笔记在这里撰写成文一为巩固知识二为展示我的学习过程及理解。文笔、排版拙劣望见谅。 力扣 一、二叉树的前序遍历1. 题目2. 递归求解3. 迭代求解 二、字典序最小回文串1.题目2.双指针实现 一、二叉树的前序遍历
二叉树的前序遍历 1. 题目 2. 递归求解 前序遍历根 — 左子树 — 右子树先访问根节点然后再分别对当前根节点的左子树和右子树重复同样的操作。中序遍历和后序遍历也都是类似的由此可以看出二叉树遍历本身就具有递归的性质。 /*** 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 ListInteger preorderTraversal(TreeNode root) {ListInteger ret new ArrayList();// 进行递归preorder(root, ret);return ret;}public void preorder(TreeNode root, ListInteger ret) {if(root null){return ;}//处理根节点ret.add(root.val);//处理左子树preorder(root.left,ret);//处理右子树preorder(root.right,ret);}
}3. 迭代求解 代码一
/*** 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 ListInteger preorderTraversal(TreeNode root) {ListInteger ret new ArrayList();if (root null) {return ret;}StackTreeNode stack new Stack();TreeNode cur root;stack.push(cur);while (!stack.isEmpty()) {// 取出栈顶元素TreeNode tmp stack.pop();ret.add(tmp.val);if (tmp.right ! null) {stack.push(tmp.right);}if (tmp.left ! null) {stack.push(tmp.left);}}return ret;}
}代码二
/*** 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 ListInteger preorderTraversal(TreeNode root) {// 创建一个 List 存储结果ListInteger ret new ArrayList();if(root null){return ret;}// 利用栈模拟实现// 创建一个栈 先进后出StackTreeNode s new Stack();TreeNode cur root;while(cur ! null || !s.isEmpty()){while(cur ! null){s.push(cur);ret.add(cur.val);cur cur.left;}//弹出栈顶元素TreeNode tmp s.pop();cur tmp.right;}return ret;}
}二、字典序最小回文串
字典序最小回文串 1.题目 2.双指针实现
可以使用双指针对给定的字符串 s 进行遍历。初始时两个指针 left 和 right 分别指向 s 的首尾。在遍历的过程中left 每次向右移动一个位置right 每次向左移动一个位置这样一来它们总是指向在最终回文字符串中必须相同的两个字母会有以下两种情况如果它们指向的字母相同我们无需进行任何操作。当两个指针指向同一个位置时也属于这一种情况如果它们指向的字母不同由于需要尽可能少的操作我们会把其中一个字母修改成与另一个字母相同。对于这一次操作我们需要让最终字符串的字典序最小因此我们应当贪心地将字典序较大的字母改成与字典序较小的字母相同。
class Solution {public String makeSmallestPalindrome(String s) {//转换为数组char[] array s.toCharArray();int left 0,right array.length - 1;while(left right){if(array[left] ! array[right]){char tmp (char)Math.min(array[left],array[right]);array[left] tmp;array[right] tmp;}left;right--;}return new String(array);}
}
