剑指offer第三天

21.栈的压入、弹出序列

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)

【解题思路】:设计一个辅助栈,如果下一个弹出的数字是辅助栈的栈顶,则弹出,如果不是栈顶,则继续将压入序列压入辅助栈,直到把下一个需要弹出的数字压入栈顶为止;如果所有数字都压入辅助站,栈顶仍然不是欲弹出的数字,则该序列不可能是一个弹出序列。

import java.util.Stack;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA == null||popA == null||pushA.length!=popA.length) return false;
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for(int i = 0 ;i<popA.length;i++){
            //一定注意这里需要先判断一下栈是否为空,
            //如果为空,则调用peek()时会出现异常;
            if(stack.empty())
                stack.push(pushA[j++]);
            while(stack.peek()!=popA[i]&&j<pushA.length)
                stack.push(pushA[j++]);
            if(stack.peek()==popA[i])
                stack.pop();
            else
                return false;
        }
        return true;
    }
}

22.从上往下打印二叉树

从上往下打印出二叉树的每个节点,同层节点从左至右打印。

Java知识点:

  1. 返回长度:
    1. String.length();String字符串用length()方法会返回其长度。
    2. Array.length;数组有length属性,直接数组名点length就可以取到。
    3. ArrayList.size()方法的会返回其长度。
  2. ArrayList 操作: get(),add(),remove() You need to use the get() method to get the element at a particular index from an ArrayList. You can't use [] to get the element at a particular index, in an arraylist. Its possible only for arrays and your files is not an array, but an ArrayList.
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.ArrayList;
/**
用arraylist模拟一个队列来存储相应的TreeNode
*/
public class Solution {
    ArrayList<Integer> result = new ArrayList<>();
    ArrayList<TreeNode> temp = new ArrayList<>();
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        if(root == null) return result;
        temp.add(root);
        while(temp.size() != 0){
            TreeNode node = temp.remove(0);
            result.add(node.val);
            if(node.left!=null)
                temp.add(node.left);
            if(node.right!=null)
                temp.add(node.right);
        }
        return result;
    }
}

23.二叉搜索树的后序遍历序列

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出True,否则输出False。假设输入的数组的任意两个数字都互不相同。

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence == null || sequence.length == 0) return false;
        int start = 0,end = sequence.length-1;
        return isSearchTree(sequence,start,end);
    }
    public boolean isSearchTree(int [] sequence,int start,int end){
        if(end==start) return true;
        int root = sequence[end];
        int index = end;
        for(int i = start;i<end;i++){
            if(sequence[i] > root){
                index = i;
                break;
            }
        }
        for(int i = index;i<end;i++)
            if(sequence[i]< root)
                return false;
        if(index == end||index == start)// index = end 时没有右子树;index = start时没有左子树; 
            return isSearchTree(sequence,start,end-1);
        else
            return isSearchTree(sequence,start,index-1)&&isSearchTree(sequence,index,end-1);
    }
}

24.二叉树中和为某一值的路径

输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 【解题思路】:因为根结点和叶子结点一定在路径中,而且路径开始一定是跟结点,使用前序遍历遍历二叉树,每经过一个结点减小target的值,直至找到使target=0的叶子结点,即为路径,每次回退,需要删除路径中最后一个结点。

import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    private ArrayList<ArrayList<Integer>> allPath = new ArrayList<>();
    private ArrayList<Integer> path = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root == null) return allPath;
        target -= root.val;
        path.add(root.val);
        if(target == 0&& root.left == null&&root.right == null)
            allPath.add(new ArrayList<Integer>(path));
        else{
            FindPath(root.left,target);
            FindPath(root.right,target);
        }
        path.remove(path.size()-1);
        return allPath;
        
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

LintCode 乱序字符串题目分析代码

给出一个字符串数组S,找到其中所有的乱序字符串(Anagram)。如果一个字符串是乱序字符串,那么他存在一个字母集合相同,但顺序不同的字符串也在S中。

1053
来自专栏机器学习从入门到成神

Java使用增强for循环和迭代器遍历Map集合

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

2901
来自专栏大闲人柴毛毛

剑指 offer代码解析——面试题37两个链表的第一个公共结点

本题的详细解析均在代码注释中: import java.util.Stack; /** * 题目:输入两个链表,找出他们的第一个公共结点 * @autho...

3155
来自专栏Java进阶之路

一道有趣的Map迭代题

2040
来自专栏LinkedBear的个人空间

唠唠SE的集合-01——Collection接口

当集合中存储的对象类型不同时,那么会导致程序在运行的时候的转型异常,所以jdk1.5加入了泛型机制。

682
来自专栏武培轩的专栏

剑指Offer-数字在排序数组中出现的次数

题目描述 统计一个数字在排序数组中出现的次数 思路 思路一:暴力,简单粗暴,但是并不可取 思路二:因为题中说是排序数组,因此我们要先想到二分查找,因此我们先用二...

2925
来自专栏Netkiller

Java 数据类型转换

本文节选自《Netkiller Java 手札》 作者:netkiller 1.5. 类型 1.5.1. String 1.5.1.1. 随机字符串 pu...

3765
来自专栏LanceToBigData

JavaSE(八)集合之List

前面一篇的corejava讲的是集合的概述,这一篇我将详细的和大家讲解一下Collection下面的List、set、queue这三个子接口。希望大家能得到提升...

25210
来自专栏向治洪

HashMap实现原理分析

HashMap实现原理分析 HashMap主要是用数组来存储数据的,我们都知道它会对key进行哈希运算,哈系运算会有重复的哈希值,对于哈希值的冲突,HashMa...

2905
来自专栏desperate633

Top 6 常见问题关于Java中的Map1 将Map转换成一个List2 遍历map中的键值对3 根据Map的key值排序4 根据Map的value值排序5 初始化一个静态的不可变的Map6 Has

我们都知道Map是一种键-值对的数据结构,每个键都是唯一的!本文讨论了关于Java中Map使用的最常见的8个问题。为了叙述的简单,所有的例子都会使用泛型。并且本...

813

扫码关注云+社区

领取腾讯云代金券