（JAVA版）leetcode算法之路树篇（一）树的遍历相关

一、题目

树的遍历相关题目做了一共14道

其中这些是两颗树的遍历对比

100. 相同的树、572. 另一棵树的子树、101. 对称二叉树

都用的深度优先搜索递归进行，分布对比两棵树的节点来返回false or true。

相同的树

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
       if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        } else if (p.val != q.val) {
            return false;
        } else {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
 
    }
}

另一个树的子树

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(subRoot==null&&root==null)
            return true;
        else if(root==null)
            return false;
        if(root.val==subRoot.val)
            return isSubtree(root.left,subRoot.left)&&isSubtree(root.right,subRoot.right);
        return isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);
    }
}

对称二叉树

class Solution {
     public boolean isSymmetric(TreeNode root){
       return check(root.left,root.right);
    }
    boolean check(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 check(p.left,q.right)&&check(p.right,q.left);
    }
}

这一类题目都能以节点是否为null和节点的值来当作结束递归的条件，当一个递归函数拥有类型不是void，可以尝试在return中进行递归。

简单代码

还有例如104. 二叉树的最大深度这道题一行代码就能解决

class Solution {
    public int maxDepth(TreeNode root) {
         return root == null ? 0 : Math.max(this.maxDepth(root.left), this.maxDepth(root.right)) + 1;
    }
}

110. 平衡二叉树则是通过先判断二叉树的深度再来递归判断

class Solution {
     public boolean isBalanced(TreeNode root) {
         return root == null || Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.right) && isBalanced(root.left);
    }
    public int depth(TreeNode root){
        return root==null?0:Math.max(depth(root.left),depth(root.right))+1;
    }
}

前中后序遍历

226. 翻转二叉树

class Solution {
     public TreeNode invertTree(TreeNode root) {
       if (root == null) {
            return null;
        }
 
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
 
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
 
}

还有一种写法

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

类似的题目543. 二叉树的直径

class Solution {
   int max=-1;
    public int diameterOfBinaryTree(TreeNode root) {
        d(root);
        return max;
    }
    public int d(TreeNode root){
        if(root==null)
            return 0;
        int left=d(root.left);
        int right=d(root.right);
        if(max<left+right)
            max=left+right;
        return Math.max(left,right)+1;
    }
}

563. 二叉树的坡度

class Solution {
    int all=0;
 
    public int findTilt(TreeNode root) {
        d(root);
        return all;
    }
    public int d(TreeNode root){
        if(root==null)
            return 0;
        int left=d(root.left);
        int right=d(root.right);
        all+=Math.abs(left-right);     
        return root.val+left+right;
    }
}

还有一些题目都大差不差：112. 路径总和、530. 二叉搜索树的最小绝对差、637. 二叉树的层平均值、653. 两数之和 IV - 输入二叉搜索树、671. 二叉树中第二小的节点、606. 根据二叉树创建字符串以上这些就是目前做过的二叉树遍历系列。

二、总结

树的遍历总体都比较简单，除去层次遍历和广度优先搜索，基本都是递归遍历+深度优先搜索，在遍历的过程去处理节点或者处理节点的左右子树，还有一种就是获取节点信息或者节点的左右子树的信息来判断

三、用到的Java知识

因为之前是用c++做的，现在转java很多东西不一样，所以记录一下

---

3.1 StringBuffer

内容可变的字符串类，使用StringBuffer来对字符串的内容进行动态操作，不会产生额外的对象。 初始时，默认是有16个字符来做为缓冲区

---

3.1.1 构造方法

new StringBuffer();

new StringBuffer(String);

new StringBuffer(int);

new StringBuffer(charSequence);

---

3.1.2 常用方法

append():在当前StringBuffer对象上，追加其他内容

capacity():返回当前容量

length():返回长度 

setCharAt(int,char):将给定索引位置的字符设置为第二个参数给定的值

reverse():将StringBuffer内容反转

delete(int,int):删除StringBuffer从指定索引开始(包含)到结束(不包含)的字符串

toString():将StringBuffer转成字符串 insert(int,Object):在指定索引位置，插入给定值 

replace(int,int,String):将指定的字符串替换到起始位置(包含)和结束位置(不包含)中

deleteCharAt(int):删除指定索引位置的字符

---

3.2 集合类Collection

3.2.1、List

List里存放的对象是有序的，同时也是可以重复的，List关注的是索引，拥有一系列和索引相关的方法，查询速度快。因为往list集合里插入或删除数据时，会伴随着后面数据的移动，所有插入删除数据速度慢。

---

3.2.1.1、ArrayList

ArrayList: 是List的一个实现类，底层数据结构是数组

构造方法：

List<String> list=new ArrayList<>();

常用方法

add(Object obj)#在集合后面加入元素,会返回一个boolean类型的值
add(int index,Object obj)#在指定索引位置前面插入一个元素
size()#获取当前集合中元素的个数
isEmpty()#判断当前集合中是否为空
clear()#从集合中删除所有元素
addAll(Collection c)#在当前集合中加入另一个集合的元素，要求两个集合使用的泛型相同
addAll(int index,Collection c)#在当前集合指定位置之前，加入另一个集合的元素
remove(int index)#移除指定索引位置的元素，并将该元素返回
remove(Object obj)#移除对应元素，如果有多个相同值，只移除第一个找到的元素，如果是整数类型，
要封装成包装类。返回boolean类型的值，是否移除成功
removeAll(Collection c)#从当前集合中移除参数集合中所有包含的元素
retainAll(Collection c)#在当前集合中保留参数集合中所有包含的元素
conatins(Object o)#判断当前集合中是否包含给定参数的元素，返回boolean类型的值
containsAll(Collection c)#判断当前集合中是否包含给定参数集合的所有元素
toArray()#以正序方式，返回一个包含所有元素的对象数组
indexOf(Object)#查找参数在当前集合中第一次出现的索引位置
lastIndexOf(Object)#查找参数在当前集合最后一次出现的索引位置
subList(int index,int end)#对当前集合进行截取，从起始位置（包含）截取到结束位置（不包含），返
回一个新的List集合
iterator()#获取集合的迭代器
listIterator()#获取集合的List迭代器
set(int index,Object obj)#设置索引位置的元素为第2个参数数据

---

 

3.2.1.2、LinkedList

LinkedList的底层使用了 双向链表

构造方法

List<Integer> list1 = new LinkedList<>();

新增方法

addFirst(Object)：将给定元素插入链表的开头
addLast(Object)：将给定元素追加到链表的尾部
getFirst()：获取链表的头结点元素值
getLst()：获取链表的尾结点元素值
removeFirst()：移除链表的头结点，并返回其中的元素值
removeLast(): 移除链表的尾结果，并返回其中的元素值

---

 3.2.1.3、Queue

在队列这种数据结构中，最先插入的元素将是最先被删除的元素；反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出”（FIFO—first in first out）的线性表。树的层次遍历会用到

LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。

构造方法

 Queue<String> queue = new LinkedList<String>();

常用方法

压入元素(添加)：add()、offer()
相同：未超出容量，从队尾压入元素，返回压入的那个元素。
区别：在超出容量时，add()方法会对抛出异常，offer()返回false
 
弹出元素(删除)：remove()、poll()
相同：容量大于0的时候，删除并返回队头被删除的那个元素。
区别：在容量为0的时候，remove()会抛出异常，poll()返回false
 
获取队头元素(不删除)：element()、peek()
相同：容量大于0的时候，都返回队头元素。但是不删除。
区别：容量为0的时候，element()会抛出异常，peek()返回null。

 

---

 

3.2.1.4、Stack

Stack的底层存储结构是数组，Stack的进出方式是后进先出，Stack实现了List接口。

构造方法

Stack<Integer> stack=new Stack<>();

常用方法 

把元素压栈：push(E)；
把栈顶的元素“弹出”：pop()；
取栈顶元素但不弹出：peek()。

---

3.2.1.5、Deque

双端队列是Java集合框架中的一种数据结构，它允许在队列两端进行元素的插入和删除操作。Deque可以看作是既支持队列操作，又支持栈操作的一种数据结构

构造方法

Deque<Integer> deque = new ArrayDeque<>();基于数组实现的双端队列
LinkedList<String> deque = new LinkedList<>();用linkedList模拟

常用方法 

void addFirst(E e)：在队列的头部插入元素。
void addLast(E e)：在队列的尾部插入元素。
boolean offerFirst(E e)：尝试在队列头部插入元素，如果成功返回true，否则返回false。
boolean offerLast(E e)：尝试在队列尾部插入元素，如果成功返回true，否则返回false。
E removeFirst()：移除并返回队列头部的元素，如果队列为空，则抛出异常。
E removeLast()：移除并返回队列尾部的元素，如果队列为空，则抛出异常。
E pollFirst()：移除并返回队列头部的元素，如果队列为空，则返回null。
E pollLast()：移除并返回队列尾部的元素，如果队列为空，则返回null。
E getFirst()：返回队列头部的元素，但不移除，如果队列为空，则抛出异常。
E getLast()：返回队列尾部的元素，但不移除，如果队列为空，则抛出异常。
E peekFirst()：返回队列头部的元素，但不移除，如果队列为空，则返回null。
E peekLast()：返回队列尾部的元素，但不移除，如果队列为空，则返回null。

---

3.2.2、Set

Set是一种集合类型，它用于存储不重复的元素

---

3.2.2.1、HashSet

底层使用HashMap，将数据存储到hashMap的key上面 特点：无序性，唯一性。 如果存储的数据具有相同的hashcode，则会调用equals方法再次进行比较 常用方法和List接口相同 没有List接口中的索引处理方式

构造方法

Set<String> set = new HashSet<>(); 

 常用方法

添加元素：add(E element) 方法用于向HashSet中添加元素。
删除元素：remove(Object element) 方法用于从HashSet中删除指定的元素。
判断元素是否存在：contains(Object element) 方法用于判断HashSet中是否包含指定的元素。
获取集合大小：size() 方法用于获取HashSet中元素的数量。
判断集合是否为空：isEmpty() 方法用于判断HashSet是否为空。
清空集合：clear() 方法用于清空HashSet中的所有元素。

---

 3.2.2.2、TreeSet

底层是基于红黑树实现的有序集合

红黑树属性：

1. 每个节点都有一个颜色属性，可以是红色或黑色。
2. 根节点是黑色的。
3. 每个叶子节点（NIL 节点，在 TreeSet 的实现中可能不显式表示）是黑色的。
4. 如果一个节点是红色的，则它的两个子节点都是黑色的。
5. 对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点

TreeSet 的内部节点通常包含一个键（key）、颜色信息、左右子节点的引用以及父节点的引用（在某些实现中可能不包括父节点的引用）。

构造方法

 TreeSet<Integer> numbers = new TreeSet<>();

 常用方法

应用场景

• 当需要保持元素的有序性且不允许重复时，TreeSet是一个很好的选择。
• 常用于需要按照特定顺序处理元素的情况

---

 

 3.2.2.3、LinkedHashSet

它继承自 HashSet，因此具有哈希表的查找性能，同时又使用链表维护元素的插入顺序

会保持元素的插入顺序，即元素被添加到集合中的顺序就是它们在集合中的顺序。且保证唯一性

构造函数

LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();
 
----------------------------------------------------------------
#从现有的集合（如 List 或 Set）创建一个 LinkedHashSet
Set<String> existingSet = new HashSet<>(Arrays.asList("A", "B", "C"));
LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>(existingSet);

 常用方法

linkedHashSet.add("D");添加元素
linkedHashSet.remove("B");删除元素
linkedHashSet.contains("C");查询元素是否存在
linkedHashSet.isEmpty()是否为空
linkedHashSet.size();获取大小
linkedHashSet.clear();清空
String[] array = linkedHashSet.toArray(new String[0]);将 LinkedHashSet 中的元素转换为数组
-------------------------------------------
#比较两个 LinkedHashSet 是否相等
LinkedHashSet<String> set1 = new LinkedHashSet<>(Arrays.asList("苹果", "香蕉", "橙子"));
LinkedHashSet<String> set2 = new LinkedHashSet<>(Arrays.asList("苹果", "香蕉", "橙子"));
boolean isEqual = set1.equals(set2); // 返回 true
 
 
 
 
 
 

---

3.3、Map

Map中的集合，元素是成对存在的。每个元素由键与值两部分组成，通过键可以找对所对应的值。

3.3.1、Hashmap

HashMap 是无序的，即不会记录插入的顺序。

HashMap基于数组和链表的结构，数组用于存储元素，链表用于解决哈希冲突

构造函数

HashMap<Integer, String> Sites = new HashMap<Integer, String>();

常用方法

put(K key, V value)： 将键（key）/值（value）映射存放到Map集合中。
 
get(Object key)： 返回指定键所映射的值，没有该key对应的值则返回 null。
 
size()： 返回Map集合中数据数量。
 
clear()： 清空Map集合。
 
isEmpty()： 判断Map集合中是否有数据，如果没有则返回true，否则返回false。
 
remove(Object key)： 删除Map集合中键为key的数据并返回其所对应value值。
 
values()： 返回Map集合中所有value组成的以Collection数据类型格式数据。
 
containsKey(Object key)： 判断集合中是否包含指定键，包含返回 true，否则返回false。
 
containsValue(Object value)： 判断集合中是否包含指定值，包含返回 true，否则返回false。
 
keySet()： 返回Map集合中所有key组成的Set集合。
 
entrySet()： 将Map集合每个key-value转换为一个Entry对象并返回由所有的Entry对象组成的Set集合
 
-------------------------------------
在Hash中可以直接使用以下方法遍历(所有键)KeySet
HashMap<String,String> map = new　HashMap<String,String>();
for (String i : map.keySet()) 
{ 
    //String 是mp中的键的对应类型 i 是对应的KeySet中的每一个键值 　
    System.out.println( map.get(i));　
}
//通过迭代器的方式遍历：
Set<Map.Entry<String,String>> set=map.entrySet();
Iterator<Map.Entry<String,String>> it=set.iterator();
while(it.hasNext()){
		Map.Entry<String,String> e=it.next();
        System.out.println(e);
}

---

3.3.2、Hashtable

Hashtable 的函数都是同步的，这意味着它是线程安全的。它的key、value都不可以为null。此外，Hashtable中的映射不是有序的

构造函数

 Hashtable<String,Integer> ht=new Hashtable()<>;

常用方法

1	void clear( )
 将此哈希表清空，使其不包含任何键。
2	Object clone( )
创建此哈希表的浅表副本。
3	boolean contains(Object value)
 测试此映射表中是否存在与指定值关联的键。
4	boolean containsKey(Object key)
测试指定对象是否为此哈希表中的键。
5	boolean containsValue(Object value)
如果此 Hashtable 将一个或多个键映射到此值，则返回 true。
6	Enumeration elements( )
返回此哈希表中的值的枚举。
7	Object get(Object key)
 返回指定键所映射到的值，如果此映射不包含此键的映射，则返回 null. 更确切地讲，如果此映射包含满足 (key.equals(k)) 的从键 k 到值 v 的映射，则此方法返回 v；否则，返回 null。
8	boolean isEmpty( )
测试此哈希表是否没有键映射到值。
9	Enumeration keys( )
 返回此哈希表中的键的枚举。
10	Object put(Object key, Object value)
将指定 key 映射到此哈希表中的指定 value。
11	void rehash( )
增加此哈希表的容量并在内部对其进行重组，以便更有效地容纳和访问其元素。
12	Object remove(Object key)
从哈希表中移除该键及其相应的值。
13	int size( )
 返回此哈希表中的键的数量。
14	String toString( )
返回此 Hashtable 对象的字符串表示形式，其形式为 ASCII 字符 ", " （逗号加空格）分隔开的、括在括号中的一组条目。

---

 

3.4、总结

数据结构实现：ArrayList（可变数组）、LinkedList（双向列表）

高层次数据结构：Queue（队列）、Deque（双端队列）、Stack（栈）、HashSet（只存键的hash表）、Hashmap（普通的hash表）

有序且不重复的值的存储的数据结构：TreeSet（红黑树实现）、LinkedHashSet