算法很美笔记（Java）——树

性质

树

上面的性质因为两个结点由一条边连成

结点数目越多，算法复杂度越高 

二叉树

 

结构

 层次遍历

利用队列，弹一个，加N个（队列里弹出一个元素，就把这个元素的所有孩子加进去）

具体来说：指针先指树根，加入队列里后，弹出队列，把他的孩子都加入，再弹，再加

二叉查找树（BST）

比root小的放左边，大的放右边

中序遍历会得到递增的有序序列

结构

// 定义二叉树节点的类
class Node {int val;Node lchild; // 左子树Node rchild; // 右子树// 构造函数，初始化节点的值和子树Node(int val) {this.val = val;this.lchild = null;this.rchild = null;}
}

// 定义二叉搜索树的类
public class BST {private Node root; // 根节点private int size;  // 节点个数// 构造函数，初始化根节点为nullpublic BST() {this.root = null;this.size = 0;}// 判断二叉搜索树是否为空public boolean isEmpty() {return root == null;}// 获取二叉搜索树的节点个数public int size() {return size;}// 清空二叉搜索树public void clear() {this.root = null;}
}

 BST类里的方法

只要有修改了树的方法，就会有返回节点，每次返回都要更新树（也就是node.rchild = method(……））

eg

删除（需要改变树）
if (val < root.val) {
            root.lchild = BSTDelete(root.lchild, val);
        } else if (val > root.val) {
            root.rchild = BSTDelete(root.rchild, val);
        } else {

添加（需要改变树）

if (val < node.val) {
            node.lchild = addNode(node.lchild, val);
        } else if (val > node.val) {
            node.rchild = addNode(node.rchild, val);
        }

搜索（不需要改变树）

} else if (val < root.val) {
            return BSTSearch(root.lchild, val);
        } else {
            return BSTSearch(root.rchild, val);

添加

都添加成树叶，不会在中间添加

// 添加节点的方法public void addNode(int val) {this.root = addNode(this.root, val);this.size++;}// 递归插入节点的方法private Node addNode(Node node, int val) {if (node == null) {return new Node(val);}if (val < node.val) {node.lchild = addNode(node.lchild, val);} else if (val > node.val) {node.rchild = addNode(node.rchild, val);}return node;}

删除

需要考虑三种情况：

1. 要删除的节点是叶子节点：直接删除该节点。
2. 要删除的节点只有一个子节点：用该子节点替换要删除的节点。
3. 要删除的节点有两个子节点：找到该节点右子树中的最小节点（即右子树中最左边的节点），用这个最小节点的值替换要删除节点的值，然后删除右子树中的最小节点。

public void BSTDelete(int val) {int originalSize = this.size;this.root = BSTDelete(this.root, val);
//因为会有树为空，删除失败的情况，所以不能直接size--if (originalSize > this.size) {this.size--;}}public Node BSTDelete(Node root, int val) {if (root == null) {return null;}
// 递归地在左子树中查找要删除的节点if (val < root.val) {root.lchild = BSTDelete(root.lchild, val);} else if (val > root.val) {
// 递归地在右子树中查找要删除的节点root.rchild = BSTDelete(root.rchild, val);}
// 找到要删除的节点else {// 情况 1: 要删除的节点没有子节点或只有一个子节点if (root.lchild == null) {return root.rchild;} else if (root.rchild == null) {return root.lchild;}// 情况 2: 要删除的节点有两个子节点// 找到右子树中的最小节点root.val = Min(root.rchild);// 删除右子树中的最小节点root.rchild = BSTDelete(root.rchild, root.val);}return root;}

搜索

public Node BSTSearch(Node root, int val) {if (root == null) {return null;}if (val == root.val) {return root;} else if (val < root.val) {return BSTSearch(root.lchild, val);} else {return BSTSearch(root.rchild, val);}}

创建

这里没有维护size

public Node BSTBuild(int[] nums) {if (nums == null || nums.length == 0) {return null;}this.root = new Node(nums[0]);for (int i = 1; i < nums.length; i++) {addNode(nums[i]);}return this.root;}

最大值

最右边的值最大

所以我们可以用一个指针p指向root，而后一直移动指针，直到p.right == null

或者用递归

    //    找最大,树的最右节点public int Max(){if (root == null){return -100000;}TreeNode node = findMax(root);return node.val;}private TreeNode findMax(TreeNode root){if(root.right == null){return root;}return findMax(root.right);}

最小值

最左边的值最小

同上

    //    找最小，树的最左节点public int Min(){if (root == null){return 100000;}TreeNode node = findMin(root);return node.val;}private TreeNode findMin(TreeNode root){if(root.left == null){return root;}return findMin(root.left);}

contains

  public boolean contains(TreeNode root, int val) {if(root == null){return false;}if(root.val == val){return true;} else if (root.val > val) {return contains(root.left,val);} else {return contains(root.right,val);}}

某节点的前驱

指的是中序遍历后的那个序列，某节点的前驱

就是比这个节点小的第一个节点

两种情况：1、是其左子树的最大值

                  2、没有左子树，则向上追溯，直到某个祖先节点是右孩子，那么这个祖先节点的父节点就是所求

某节点的后继

指的是中序遍历后的那个序列，某节点的后继

就是比这个节点大的第一个节点

两种情况：1、是其右子树的最小值

                  2、没有右子树，则向上追溯，直到某个祖先节点是左孩子，那么这个祖先节点的父节点就是所求

某节点高度

递归得到左右子树的高度，取较高的一方+1就是某节点的高度

public int getHeight(Node node) {if (node == null) return 0;int l = getHeight(node.left);int r = getHeight(node.right);return 1 + Math.max(l, r);}

层次遍历

与树的层次遍历思路一致，只不过孩子列表明确成了左右孩子

平衡二叉树（AVL）

左右子树的高度差（平衡因子）不大于1

AVL也是BST，只不过多了一个高度差的特点，所以基本操作实现思路按BST进行就行，同时考虑不同点即可，这里，我们直接复用BST的操作

平衡因子

public int getHeight(Node node) {if (node == null) return 0;return 1 + Math.max(getHeight(node.lchild), getHeight(node.rchild));}
public int getBalanceFactor(Node node) {if (node == null) {return 0;}int leftHeight = getHeight(node.left);int rightHeight = getHeight(node.right);return leftHeight - rightHeight;}

如果节点结构里有height，则可以直接调用：

但是如果这个节点是改变后的，想要更新height，就只能用上面的，不能用下面这个方法（记录过的height）

   //获取当前节点的高度public int getHeight(Node node){if (node==null){return 0;}return node.height;}//获取当前节点的平衡因子public int getBalanceFactor(Node node){if (node==null){return 0;}return getHeight(node.left)-getHeight(node.right);}

添加

先复用BST的插入，再调整平衡

 // AVL 插入操作public void insert(int val) {root = bstInsert(root, val);root = balanceTree(root);}

删除

// AVL 删除操作public void delete(int val) {root = bstDelete(root, val);root = balanceTree(root);}

调整平衡

判断不平衡类型的关键在于当前不平衡节点（平衡因子为 -2 或 2 的节点）及其子节点的平衡因子。

1. LL 型

• 判断条件：当前不平衡节点的平衡因子为 2，且其左子节点的平衡因子为 1。
• 调整方法：右旋

2. LR 型

• 判断条件：当前不平衡节点的平衡因子为 2，且其左子节点的平衡因子为 -1。
• 调整方法：左旋+右旋

3. RR 型

• 判断条件：当前不平衡节点的平衡因子为 -2，且其右子节点的平衡因子为 -1。
• 调整方法：左旋

4. RL 型

• 判断条件：当前不平衡节点的平衡因子为 -2，且其右子节点的平衡因子为 1。
• 调整方法：右旋+左旋

检查每个节点（用递归来实现）是否平衡，不平衡就调整 

/ 调整树的平衡public Node balanceTree(Node node) {if (node == null) {return node;}node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));int balance = getBalanceFactor(node);// LL 型if (balance > 1 && getBalanceFactor(node.left) >= 0) {return rightRotate(node);}// LR 型if (balance > 1 && getBalanceFactor(node.left) < 0) {node.left = leftRotate(node.left);return rightRotate(node);}// RR 型if (balance < -1 && getBalanceFactor(node.right) <= 0) {return leftRotate(node);}// RL 型if (balance < -1 && getBalanceFactor(node.right) > 0) {node.right = rightRotate(node.right);return leftRotate(node);}return node;}

右旋和左旋

// 右旋操作private Node rightRotate(Node y) {
//        实际上就是x和y的位置要改变，
//        让x成为y的父节点
//        没改变前y是x的父节点Node x = y.left;
//        如果有T2，就连给y，没有的话T2就是null，y的左孩子就是nullNode T2 = x.right;x.right = y;y.left = T2;
//      更新高度y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;return x;}// 左旋操作private Node leftRotate(Node x) {Node y = x.right;Node T2 = y.left;y.left = x;x.right = T2;x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;return y;}

带parent的AVL

方法具体实现看这篇文章：https://blog.csdn.net/jarvan5/article/details/112428036

题（未完待续）

叶子节点的个数

public int count(Node root) {if (root == null) {return 0;} else if (root.left == null && root.right == null) {return 1;}return count(root.left) + count((root.right));}

第k层的节点数

一个节点的孩子节点的上一层就是这个节点所在层

所以计算第k层所有节点的孩子节点的上一层结点数，即为所求

public int countK(Node root,int k) {if (root == null) {return 0;}if(k == 1) {return 1;}return countK(root.left , k-1) + countK(root.right , k-1);}

是否是完全二叉树

是否相同

要判断两棵树是否相同，必须同时满足以下两个条件：

1. 结构相同：两棵树的节点位置和父子关系必须一致。

2. 节点值相同：对应位置的节点值必须相等。

递归

public boolean isSameTree(Node p, Node q) {// 如果两个节点都为空，则相同if (p == null && q == null) {return true;}// 如果一个节点为空，另一个不为空，则不同if (p == null || q == null) {return false;}// 比较当前节点的值if (p.val != q.val) {return false;}// 递归比较左右子树return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}

迭代

public boolean isSameTree(Node p, Node q) {// 使用栈来存储需要比较的节点对Stack<Node[]> stack = new Stack<>();stack.push(new Node[]{p, q});while (!stack.isEmpty()) {Node[] nodes = stack.pop();Node node1 = nodes[0];Node node2 = nodes[1];// 如果两个节点都为空，继续比较下一对节点if (node1 == null && node2 == null) {continue;}// 如果一个节点为空，另一个不为空，则不同if (node1 == null || node2 == null) {return false;}// 比较当前节点的值if (node1.val != node2.val) {return false;}// 将左右子节点对压入栈中stack.push(new Node[]{node1.left, node2.left});stack.push(new Node[]{node1.right, node2.right});}return true;}

注意：

中序遍历的结果不能唯一确定一棵树的结构，因此不能直接用来判断两棵树是否相同

反例

但中序遍历搭配前序或者后序遍历，即可唯一确定一棵树

所以可以比较两种遍历的结果是否一致，一致就相同

但这样需要开辟空间存遍历结果，所以这种方法不太好（List<Integer>存结果，return pPreOrder.equals(qPreOrder) && pInOrder.equals(qInOrder); 比较）

存结果

是否镜像

判断相同是left和left比，right和right比

判断镜像是left和right比，right和left比

public boolean isMirrorTree(Node p, Node q) {// 如果两个节点都为空，则相同if (p == null && q == null) {return true;}// 如果一个节点为空，另一个不为空，则不同if (p == null || q == null) {return false;}// 比较当前节点的值if (p.val != q.val) {return false;}// 递归比较左右子树return isMirrorTree(p.left, q.right) && isMirrorTree(p.right, q.left);
}

翻转二叉树（二叉树的镜像）

左右反转二叉树的节点

public Node reverseTree(Node root) {
//        从下到上翻转if (root == null) {return null;}// 交换当前节点的左右子节点Node temp = root.left;root.left = root.right;root.right = temp;// 递归地反转左子树reverseTree(root.left);// 递归地反转右子树reverseTree(root.right);return root;}

前序遍历

public void pre(Node root) {if (root == null) {return;}System.out.print(root.val + " ");pre(root.left);pre(root.right);}

后序遍历

public void post(Node root) {if (root == null) {return;}post(root.left);post(root.right);System.out.print(root.val + " ");}

BST区间搜索

给定一个区间范围，返回所有在这个区间的值