递归算法的学习：
递归算法的学习：
递归的终止条件和递归的过程
二叉树的增删改查的算法
二叉树的四种遍历
递归算法的leetcode练习题目:
递归的终止条件和递归的过程 二叉树的增删改查的算法/**
* Copyright (C), 2018-2020
* FileName: BinaryTree
* Author: xjl
* Date: 2020/3/25 17:10
* Description: 二叉树
*/
package Tree;
import Queue.QueueLink;
public class BinaryTree {
//成员变量
//记录的是更根节点
private Node root;//这里是表示的根节点
//节点的个数
private int N;
//表示二叉树中的一个节点
private class Node {
//存储键
public Key key;
//存储的值
public Value value;
//左节点
public Node left;
//右节点
public Node right;
public Node(Key key, Value value, Node left, Node right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
//构造函数
public BinaryTree() {
this.N = 0;
}
//成员函数
public int size() {
return N;
}
//向树中的插入键值对
public void put(Key key, Value value) {
root = put(root, key, value);
}
//给指定的数中添加键值对key-value 并返回添加后的新树 传递给的插上是当前的额这个节点 和需要插入的键值
// 要插入的是key-value
public Node put(Node x, Key key, Value value) {
//子树为空 新建这个节点并返回这个节点作为树的根节点
if (x == null) {
N++;
return new Node(key, value, null, null);
}
//子树不为空
//比较节点的键值和插入的key的大小
int crp = (int) key.compareTo((Key) x.key);// key的大于节点的值
if (crp > 0) {
//key>x.key x表示的是节点 插入的值比节点值大 那就应该是放置在右边的这个地方
//x.right=put(x.right,key,value) 表示的是去插入到想 x的右节点？
x.right = put(x.right, key, value);
} else if (crp < 0) {
//如果key 0) {
//如果是key大于节点的key 这找到右子树 x.right 表示的x的整个右边的节点
return (Value) get(x.right, key);
} else if (crp < 0) {
//如果是key小于节点的key 这找到左子树
return (Value) get(x.left, key);
} else {
//如果等于key的的返回这个value
return (Value) x.value;
}
}
//删除该树中的key的value的值
public void delete(Key key) {
delete(root, key);
}
//删除指定树中的key的value的值 并返回这个删除后的树 那应该是返回的是根节点的值
public Node delete(Node x, Key key) {
//x树为null
if (x == null) {
return null;
}
//x树不为null
int cmp = key.compareTo((Key) x.key);
if (cmp > 0) {
//如果是key大于节点的key 这找到右子树 x.right 表示的x的整个右边的节点
x.right = delete(x.right, key);
} else if (cmp < 0) {
//如果是key小于节点的key 这找到左子树
x.left = delete(x.left, key);
} else {
//让元素个数减少
N--;
//如果等于key的的x的键的时候，那么就需要完成是的是删除这个节点的操作
//找到右子树中的小的节点
if (x.right == null) {
return x.left;
}
if (x.right == null) {
return x.right;
}
//找到右子树的最小的节点
Node minnode = x.right;
while (minnode.left != null) {
minnode = minnode.left;
}
//删除右子树的最小的点
Node n = x.right;
while (n.left != null) {
if (n.left.left != null) {
//断开节点
n.left = null;
} else {
//变换节点为下一个就可以
n = n.left;
}
}
//让x的节点的左子树minnode的左子树
minnode.left = x.left;
//让x的节点的右子树minnode的右子树
minnode.right = x.right;
//让x的节点的父节点指向minnode
x = minnode;
}
return x;
}
//查找树的最小的键 就会一直找到左边的值 然后在这个节点 并返回这个
public Key minkey() {
return (Key) minNode(root).key;
}
//查找树的最小的键对应的值 就会一直找到左边的值 然后在这个节点 并返回这个
public Value minValue() {
return (Value) minNode(root).value;
}
//找到最小的键在节点
public Node minNode(Node x) {
if (x.left != null) {
return minNode(x.left);
} else {
return x;
}
}
public Key maxkey() {
return (Key) minNode(root).key;
}
//查找树的最大的键对应的值 就会一直找到左边的值 然后在这个节点 并返回这个
public Value maxValue() {
return (Value) minNode(root).value;
}
//找到最大的键在节点
public Node maxNode(Node x) {
if (x.right != null) {
return maxNode(x.right);
} else {
return x;
}
}
/**
* //二叉树的遍历的方式
* @return
*/
//前序遍历
//获取整个树的键
public QueueLink preErgodic() {
QueueLink keys = new QueueLink();
preErgodic(root, keys);
return keys;
}
//获取指定的数x的所有的键，并放置在keys中
private void preErgodic(Node x, QueueLink keys) {
//如果树为空的话
if (x == null) {
return;
}
//如果树不为空的话 将节点的key记性入队的操作
keys.push((Key) x.key);
if (x.left != null) {
//如果左子树不为空则 将递归左子树
preErgodic(x.left, keys);
}
if (x.right != null) {
//如果右子树不为空则 将递归右子树
preErgodic(x.right, keys);
}
}
//中序遍历
//获取整个树的键
public QueueLink midErgodic() {
QueueLink keys = new QueueLink();
midErgodic(root, keys);
return keys;
}
//获取指定的数x的所有的键，并放置在keys中
private void midErgodic(Node x, QueueLink keys) {
//如果树为空的话
if (x == null) {
return;
}
//将左子树的放置
if (x.left != null) {
midErgodic(x.left, keys);
}
//将当前子树的放置
keys.push((Key) x.value);
//将右子树的放置
if (x.right != null) {
midErgodic(x.right, keys);
}
}
//后序遍历
//获取整个树的键
public QueueLink afterErgodic() {
QueueLink keys = new QueueLink();
afterErgodic(root, keys);
return keys;
}
private void afterErgodic(Node x, QueueLink keys) {
//如果树为空的话
if (x == null) {
return;
}
//将左子树的放置
if (x.left != null) {
afterErgodic(x.left, keys);
}
//将右子树的放置
if (x.right != null) {
afterErgodic(x.right, keys);
}
//将当前子树的放置
keys.push((Key) x.value);
}
//层序遍历的方法
public QueueLink layerErgodic() {
//定义两个队列
QueueLink keys = new QueueLink();
QueueLink nodes = new QueueLink();
nodes.push(root);
while (!nodes.isEmpty()) {
//从队列中的弹出节点 把节点中的key放置keys中
Node node = nodes.pop();
keys.push((Key) node.key);
//判断当前节点有没有左边的节点 如果有 则放入到nodes中
if (node.left != null) {
nodes.push(node.left);
}
//判断当前的节点有没有右节点 如果有 则放入到nodes中
if (node.right != null) {
nodes.push(node.right);
}
}
return keys;
}
//获取整个树的最大深度
public int maxDepth() {
return maxDepth(root);
}
//获取指定树的深度
private int maxDepth(Node x) {
if (x == null) {
return 0;
}
//x的最大深度
int max = 0;
//左子树的最大深度
int maxl = 0;
//右子树的最大深度
int maxr = 0;
//计算左子树的最大深度
if (x.left != null) {
maxl = maxDepth(x.left);
}
//计算右子树的最大深度
if (x.right != null) {
maxr = maxDepth(x.right);
}
//比较左字树和右子树的最大的深度 在加1就可以满足既可以
max = maxl > maxr ? maxl + 1 : maxr + 1;
return max;
}
}
//前序遍历
//获取整个树的键
public QueueLink preErgodic() {
QueueLink keys = new QueueLink();
preErgodic(root, keys);
return keys;
}
//获取指定的数x的所有的键，并放置在keys中
private void preErgodic(Node x, QueueLink keys) {
//如果树为空的话
if (x == null) {
return;
}
//如果树不为空的话 将节点的key记性入队的操作
keys.push((Key) x.key);
if (x.left != null) {
//如果左子树不为空则 将递归左子树
preErgodic(x.left, keys);
}
if (x.right != null) {
//如果右子树不为空则 将递归右子树
preErgodic(x.right, keys);
}
}
//中序遍历
//获取整个树的键
public QueueLink midErgodic() {
QueueLink keys = new QueueLink();
midErgodic(root, keys);
return keys;
}
//获取指定的数x的所有的键，并放置在keys中
private void midErgodic(Node x, QueueLink keys) {
//如果树为空的话
if (x == null) {
return;
}
//将左子树的放置
if (x.left != null) {
midErgodic(x.left, keys);
}
//将当前子树的放置
keys.push((Key) x.value);
//将右子树的放置
if (x.right != null) {
midErgodic(x.right, keys);
}
}
//后序遍历
//获取整个树的键
public QueueLink afterErgodic() {
QueueLink keys = new QueueLink();
afterErgodic(root, keys);
return keys;
}
private void afterErgodic(Node x, QueueLink keys) {
//如果树为空的话
if (x == null) {
return;
}
//将左子树的放置
if (x.left != null) {
afterErgodic(x.left, keys);
}
//将右子树的放置
if (x.right != null) {
afterErgodic(x.right, keys);
}
//将当前子树的放置
keys.push((Key) x.value);
}
//层序遍历的方法
public QueueLink layerErgodic() {
//定义两个队列
QueueLink keys = new QueueLink();
QueueLink nodes = new QueueLink();
nodes.push(root);
while (!nodes.isEmpty()) {
//从队列中的弹出节点 把节点中的key放置keys中
Node node = nodes.pop();
keys.push((Key) node.key);
//判断当前节点有没有左边的节点 如果有 则放入到nodes中
if (node.left != null) {
nodes.push(node.left);
}
//判断当前的节点有没有右节点 如果有 则放入到nodes中
if (node.right != null) {
nodes.push(node.right);
}
}
return keys;
}leetcode104 二叉树的最大深度（）：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
//分别获取左子树和右子树的最大的深度 然后选择其中最大的加1就可以
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
int leftDepth=maxDepth(root.left);
int rightDepth=maxDepth(root.right);
return Math.max(leftDepth,rightDepth)+1;
}
}111. 二叉树的最小深度
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if(root == null) return 0;
//这道题递归条件里分为三种情况
//1.左孩子和有孩子都为空的情况，说明到达了叶子节点，直接返回1即可
if(root.left == null && root.right == null) return 1;
//2.分别计算左孩子和右孩子
int m1 = minDepth(root.left);
int m2 = minDepth(root.right);
//这里其中一个节点为空，说明m1和m2有一个必然为0，所以可以返回m1 + m2 + 1;
if(root.left == null || root.right == null) return m1 + m2 + 1;
//3.最后一种情况，也就是左右孩子都不为空，返回最小深度+1即可
return Math.min(m1,m2) + 1;
}
}226. 翻转二叉树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
//递归终止的条件
if(root==null){
return null;
}
//递归的过程是
invertTree(root.left);
invertTree(root.right);
TreeNode temp=root.right;
root.right=root.left;
root.left=temp;
//返回这个主节点
return root;
}
}100. 相同的树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
// p and q are both null
if (p == null && q == null) return true;
// one of p and q is null
if (q == null || p == null) return false;
if (p.val != q.val) return false;
return isSameTree(p.right, q.right) &&isSameTree(p.left, q.left);
}
}101. 对称二叉树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
//或者是采用的stack的数据结构来实现这个 分别是前序遍历和后序遍历的结果是否一样
public boolean isSymmetric(TreeNode root) {
return isMirror(root, root);
}
public boolean isMirror(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) return false;
return (t1.val == t2.val)&& isMirror(t1.right, t2.left)&& isMirror(t1.left, t2.right);
}
}112. 路径总和
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if(root==null){
return false;
}
//递归的终止条件
if(root.left==null&&root.right==null){
return root.val==sum;
}
//递归的实现过程
if(hasPathSum(root.left,sum-root.val)){
return true;
}
if(hasPathSum(root.right,sum-root.val)){
return true;
}
return false;
}
}404. 左叶子之和
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int result=0;
public int sumOfLeftLeaves(TreeNode root) {
//终止条件
if(root==null){
return 0;
}
if(root.left==null&&root.right==null){
return 0;
}
//当前节点的左孩子是不是叶子节点（叶子结点：没有左右孩子）
if(root.left != null && (root.left.left == null && root.left.right == null)){
result +=root.left.val;
}
//递归条件
sumOfLeftLeaves(root.left);
sumOfLeftLeaves(root.right);
return result;
}
}257. 二叉树的所有路径
