织梦如何做视频网站,wordpress的地址在本地,网络营销是什么工作内容,哪个网站做ppt能赚钱目录 概念解释
栈 队列
树
树的概念 结点的分类
有序树
无序树
森林
二叉树
满二叉树
完全二叉树 二叉排序树
平衡二叉树
1.用栈实现队列
解法#xff1a;双栈 2.字符串解码 解法#xff1a;栈
3.二叉树的中序遍历 解法一#xff1a;递归
解法二#xff…目录 概念解释
栈 队列
树
树的概念 结点的分类
有序树
无序树
森林
二叉树
满二叉树
完全二叉树 二叉排序树
平衡二叉树
1.用栈实现队列
解法双栈 2.字符串解码 解法栈
3.二叉树的中序遍历 解法一递归
解法二迭代
4.二叉树的前序遍历
解法一递归 解法二迭代
5.二叉树的后序遍历 6.平衡二叉树
自底向上的递归
7.二叉树的最大深度 解法一迭代
解法二递归
8.对称二叉树
解法一递归
解法二迭代 概念解释
栈 栈堆栈 后进先出的结构Last In First Out,简称LIFO结构。 队列 先进先出的结构First In First Out,简称FIFO结构。 树 树(Tree)是nn 0个结点的有限集合当n0时称为空树。 在任意一个非空树中应满足 1.有且仅有一个特定的称为根(Root)的结点。 2.当n1时其余节点可分成m(m0)个互不相交的有限集合T1,T2,...Tm其中每个集合本身又是一棵树并且称为根结点的子树(SubTree)。 树的概念 结点的度结点拥有的子树的数量 结点的深度层次从上往下数结点距离根结点的距离。 结点的高度从下往上数结点在第几层结点的高度就是多少 树的高度结点深度最大的那个结点的深度就是树的深度 树的度树中度最大结点的度就是树的度。 结点的分类 叶子节点度为0的结点 分支结点内部结点度不为0的结点除根节点。 有序树 从逻辑上看树中结点的各子树从左至右是有次序的不能互换。 无序树 从逻辑上看树中结点的各子树从左至右是无次序的可以互换。 森林 m(m0)棵互不相交的树的集合。 二叉树 二叉树是n(n0)个结点的有限集合 可以是空二叉树即n0; 可以是由一个根节点和两个互不相交的树被称为根的左子树和右子树组成。 左子树和右子树又分别是一课二叉树。、 特点每个结点最多只有两棵子树 左右子树不能颠倒二叉树是有序树 满二叉树 每层结点的个数都达到最大值即如果一个二叉树的层数为k并且总结点数位-1那么这个数就是满二叉树。 特点1.最后一层都是叶子节点 2.不存在度为1的结点 3.按层序从1开始编号结点i的左孩子为2i右孩子为2i1 结点i的父结点为i/2向下取整。 完全二叉树 当且仅当其每个结点都与满二叉树中编号位1-n的结点一一对应时称为完全二叉树。 即相比于满二叉树完全二叉树少一个右下角。 特点1.只有最后两层可能又叶子结点 2.最多只有一个度为1的结点 3.按层序从1开始编号结点i的左孩子为2i右孩子为2i1 结点i的父结点为i/2向下取整。 4.如果一个完全二叉树的有n个结点那么当结点的编号in/2向下取整那么这些结点为分支结点当结点的编号in/2向下取整那么这些结点为叶子结点 二叉排序树 左子树上所有结点的关键字均小于根节点的关键字右子树上所有结点的关键字均大于根节点的关键字左子树和右子树又各是一棵二叉排序树。 平衡二叉树 树上任一结点的左子树和右子树的深度之差不超过1. 1.用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty
实现 MyQueue 类
void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并返回元素int peek() 返回队列开头的元素boolean empty() 如果队列为空返回 true 否则返回 false
说明
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque双端队列来模拟一个栈只要是标准的栈操作即可 进阶
你能否实现每个操作均摊时间复杂度为 O(1) 的队列换句话说执行 n 个操作的总时间复杂度为 O(n) 即使其中一个操作可能花费较长时间。
解法双栈 利用双栈就可以实现队列一个做输入栈一个做输出栈。 队列是先进先出栈刚好相反但如果先把数据压入输入栈再从输入栈将数据压入输出栈就和队列一样了。 class MyQueue {private static StackInteger inStack;private static StackInteger outStack;public MyQueue() {inStack new StackInteger();outStack new StackInteger();}public void push(int x) {inStack.push(x);}public int pop() {if(outStack.isEmpty()){inToOut();}return outStack.pop();}private void inToOut(){//如果输入栈非空将输入栈的元素弹出然后压入输出栈while(!inStack.isEmpty()){outStack.push(inStack.pop());}}public int peek() {if(outStack.isEmpty()){inToOut();}return outStack.peek();}public boolean empty() {return inStack.isEmpty() outStack.isEmpty();}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj new MyQueue();* obj.push(x);* int param_2 obj.pop();* int param_3 obj.peek();* boolean param_4 obj.empty();*/ 2.字符串解码
给定一个经过编码的字符串返回它解码后的字符串。
编码规则为: k[encoded_string]表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的输入字符串中没有额外的空格且输入的方括号总是符合格式要求的。
此外你可以认为原始数据不包含数字所有的数字只表示重复的次数 k 例如不会出现像 3a 或 2[4] 的输入。 解法栈 本题考查我们对栈的操作。 以3[a]2[bc]为例我们从3开始入栈 如果是数字将数字进行解析然后进栈 如果是 [ 或者 字母直接进栈 如果是 ] 开始出栈直到遇到 [ 为止。 class Solution {public String decodeString(String s) {//存数字的栈StackInteger countStack new Stack();//存字母或 [ ] 的栈StackString resStack new Stack();//初始下标int index 0;int len s.length();String res ;while(index len){char ch s.charAt(index);//处理数字if(Character.isDigit(ch)){StringBuffer sb new StringBuffer();//如果是数字就加到sb中while(Character.isDigit(s.charAt(index))){sb.append(s.charAt(index));}countStack.push(Integer.parseInt(sb.toString()));}else if(ch [){//当ch为[ 时让res入栈将res置空resStack.push(res);res ;index;}else if(ch ]){//当ch为]时开始出栈StringBuffer temp new StringBuffer(resStack.pop());int repeaTims countStack.pop();for(int i 0;irepeaTims;i){temp.append(res);}res temp.toString();index;}else{//当ch为字母时拼接到res后面res s.charAt(index);}}return res;}
}
3.二叉树的中序遍历
给定一个二叉树的根节点 root 返回 它的 中序 遍历 。
进阶: 递归算法很简单你可以通过迭代算法完成吗 解法一递归 首先我们要知道二叉树的中序遍历是什么根节点-左子树-右子树而且在访问左子树或右子树时还是同样的方式直到整个树遍历完终止条件就是当结点为空时中止。 /*** 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 inorderTraversal(TreeNode root) {ListInteger res new ArrayList();accessTree(root,res);return res;}public void accessTree(TreeNode root,ListInteger res){if(root null){return;}accessTree(root.left,res);res.add(root.val);accessTree(root.right,res);}
} 时间复杂度O(n) 空间复杂度O(n)
解法二迭代 题目要求使用迭代。 首先我们要明确中序遍历的步骤左、根、右所以先访问左子树但是根节点的值需要保存下来因为我们为了效率必须保证每个结点只访问了一次。 我们引入一个栈用来保存根节点。 迭代步骤先将根节点压入栈然后访问左子树如果左子树不为空继续将左子树的根节点压入栈如果左子树为空将其弹出栈然后输出在访问右子树直到整个树遍历完。 public ListInteger inorderTraversal(TreeNode root) {ListInteger res new ArrayList();StackTreeNode stack new Stack();while(root ! null || !stack.isEmpty()){while(root!null){stack.push(root);root root.left;}root stack.pop();res.add(root.val);root root.right;}return res;} 时间复杂度O(n) 空间复杂度O(n)
4.二叉树的前序遍历 给你二叉树的根节点 root 返回它节点值的 前序 遍历。 和中序遍历思路一样。 要注意的是遍历顺序根节点、左子树、右子树 解法一递归
public ListInteger preorderTraversal(TreeNode root) {ListInteger res new ArrayList();accessTree(root,res);return res;}public void accessTree(TreeNode root,ListInteger res){//终止条件if(rootnull){return;}//先访问根节点res.add(root.val);//左子树accessTree(root.left,res);//右子树accessTree(root.right,res);} 时间复杂度O(n) 空间复杂度O(n) 解法二迭代
public ListInteger preorderTraversal(TreeNode root) {ListInteger res new ArrayList();StackTreeNode stack new Stack();while(root!null || !stack.isEmpty()){while(root!null){res.add(root.val);stack.push(root);root root.left;}root stack.pop();root root.right;}return res;} 时间复杂度O(n) 空间复杂度O(n)
5.二叉树的后序遍历
给你一棵二叉树的根节点 root 返回其节点值的 后序遍历 。
进阶递归算法很简单你可以通过迭代算法完成吗 递归跟前两个思路一样但是迭代就差很多这是因为后序遍历的步骤是左子树、右子树、根节点每次需要遍历右子树时都需要借助根结点所以这里需要定义一个空结点每次都要保存根节点。 class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();if (root null) {return res;}DequeTreeNode stack new LinkedListTreeNode();TreeNode prev null;while (root ! null || !stack.isEmpty()) {while (root ! null) {stack.push(root);root root.left;}root stack.pop();if (root.right null || root.right prev) {res.add(root.val);prev root;root null;} else {stack.push(root);root root.right;}}return res;}
} 6.平衡二叉树
给定一个二叉树判断它是否是高度平衡的二叉树。
本题中一棵高度平衡二叉树定义为 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 自底向上的递归
public boolean isBalanced(TreeNode root) {return height(root) ! -1;}public int height(TreeNode root){if(root null){return 0;}//从左子树开始判断int leftH height(root.left);int rightH height(root.right);if(leftH -1 || rightH -1 || (leftH-rightH) 1||(rightH-leftH)1){return -1;}return leftH rightH ? (leftH 1):(rightH 1);} 7.二叉树的最大深度
给定一个二叉树 root 返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 解法一迭代 使用队列里存放当前层的所有节点。每次拓展下一层的时候我们需要将队列里的所有节点都拿出来进行拓展这样能保证每次拓展完的时候队列里存放的是当前层的所有节点即我们是一层一层地进行拓展最后我们用一个变量 ans\textit{ans}ans 来维护拓展的次数 public int maxDepth(TreeNode root) {if(root null){return 0;}QueueTreeNode q new LinkedList();int count 0;q.offer(root);while(!q.isEmpty()){int size q.size();while(size0){TreeNode n q.poll();if(n.left ! null){q.offer(n.left);}if(n.right!null){q.offer(n.right);}size--;}count;}return count;} 解法二递归 如果我们知道了左子树和右子树的最大深度 l和 r那么该二叉树的最大深度即为 max(l,r)1. 而左子树和右子树的最大深度又可以以同样的方式进行计算。 public int maxDepth(TreeNode root) {if(root null){return 0;}int l maxDepth(root.left);int r maxDepth(root.right);return l r ? l 1 : r 1;} 8.对称二叉树
给你一个二叉树的根节点 root 检查它是否轴对称。 解法一递归 乍一看使用递归很好解决。 根据题目的描述镜像对称就是左右两边相等也就是左子树和右子树是相当的。 注意这句话左子树和右子相等也就是说要递归的比较左子树和右子树。 class Solution {public boolean isSymmetric(TreeNode root) {if(rootnull) {return true;}return dfs(root.left,root.right);}boolean dfs(TreeNode left, TreeNode right) {if(leftnull rightnull) {return true;}if(leftnull || rightnull) {return false;}if(left.val!right.val) {return false;}return dfs(left.left,right.right) dfs(left.right,right.left);}
} 解法二迭代 首先我们引入一个队列。初始化时我们把根节点入队两次。每次提取两个结点并比较它们的值队列中每两个连续的结点应该是相等的而且它们的子树互为镜像然后将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时或者我们检测到树不对称即从队列中取出两个不相等的连续结点时该算法结束。 class Solution {public boolean isSymmetric(TreeNode root) {return check(root, root);}public boolean check(TreeNode u, TreeNode v) {QueueTreeNode q new LinkedListTreeNode();q.offer(u);q.offer(v);while (!q.isEmpty()) {u q.poll();v q.poll();if (u null v null) {continue;}if ((u null || v null) || (u.val ! v.val)) {return false;}q.offer(u.left);q.offer(v.right);q.offer(u.right);q.offer(v.left);}return true;}
}
