数据结构 --- 树

1、二叉树

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

每个结点最多有两棵子树，即二叉树不存在度大于2的结点。
二叉树的子树有左右之分，其子树的次序不能颠倒。

在这里插入图片描述

2、二叉树的遍历 --- 深度优先

深度优先可以分为以下三种

1、前序遍历

规则：

先访问该节点
在访问左子树
在访问右子树

上述遍历顺序：1、2、4、3、5、6

    public void preOrder(TreeNode root) {// 递归结束条件if (root == null) {return;}// 当前节点System.out.println(root);// 左子树TreeNode left = root.left;preOrder(left);// 右子树TreeNode right = root.right;preOrder(right);}

    public void preOrder1(TreeNode root) {TreeNode curr = root;Stack<TreeNode> stack = new Stack<>();while (curr != null || stack.isEmpty()) {if (curr != null) {// 处理逻辑，处理当前节点System.out.println(curr); // 利用栈，记录来的时候的顺序stack.push(curr);// 遍历左子树curr = curr.left;} else {// 从栈中弹出元素，遍历右子树TreeNode pop = stack.pop();curr = pop.right;}}}

2、中序遍历

规则：

先访问左子树
在访问该节点
在访问右子树

上述遍历顺序：4、2、1、5、3、6

    public void inOrder(TreeNode root) {// 递归结束条件if (root == null) {return;}// 左子树TreeNode left = root.left;inOrder(left);// 当前节点System.out.println(root);// 右子树TreeNode right = root.right;inOrder(right);}

    public void inOrder1(TreeNode root) {TreeNode curr = root;Stack<TreeNode> stack = new Stack<>();while (curr != null || stack.isEmpty()) {if (curr != null) {// 利用栈，记录来的时候的顺序stack.push(curr);// 遍历左子树curr = curr.left;} else {// 处理逻辑，处理当前节点System.out.println(curr);// 从栈中弹出元素，遍历右子树TreeNode pop = stack.pop();curr = pop.right;}}}

3、后续遍历

规则：

先访问左子树
在访问右子树
在访问该节点

上述遍历顺序：4、2、5、6、3、1

    public void postOrder(TreeNode root) {// 递归结束条件if (root == null) {return;}// 左子树TreeNode left = root.left;postOrder(left);// 右子树TreeNode right = root.right;postOrder(right);// 当前节点System.out.println(root);}

    public void postOrder1(TreeNode root) {TreeNode curr = root;Stack<TreeNode> stack = new Stack<>();TreeNode pop = null; // 记录最近一次弹出栈的元素while (curr != null || stack.isEmpty()) {if (curr != null) {// 利用栈，记录来的时候的顺序stack.push(curr);// 遍历左子树curr = curr.left;} else {// 从栈中弹出元素，遍历右子树TreeNode peek = stack.peek();// 判断栈顶元素的右子树是否处理，如果已经处理，就可以弹出栈if (peek.right == null || peek.right == pop) {pop = stack.pop();// 处理逻辑，处理当前节点System.out.println(pop.val);} else {curr = peek.right;}}}}

例题：

101. 对称二叉树

给你一个二叉树的根节点 root ，检查它是否轴对称。

解题思路

轴对称，其实就是左右两边子树是否对称
从根节点开始，比较左子节点和右子节点是否相等
比较左子节点的左子节点和右子节点的右子节点是否相等
比较左子节点的左右子节点和右子节点的右左子节点是否相等

有点绕，需要慢慢体会。

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

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

解题思路：

递归：

找到左子树的深度和右子树的深度较大的哪一个。然后加一。
class Solution {public int maxDepth(TreeNode root) {if(root==null){return 0;}else {int leftHeight=maxDepth(root.left);int rightHeight=maxDepth(root.right);return Math.max(leftHeight,rightHeight)+1;}}
}

BFS层序遍历

层序遍历，知道多少层，就知道最大深度了。

public class Test104 {public int maxDepth(TreeNode root) {if (root == null) {return 0;}Queue<TreeNode> queue = new ArrayDeque<>();queue.offer(root);int level = 0;while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {TreeNode poll = queue.poll();if (poll.left != null) {queue.offer(poll.left);}if (poll.right != null) {queue.offer(poll.right);}}level++;}return level;}
}

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

解题1：

递归，但是要注意一点，如果左右子树为null的时候，就不应该计算进去。
    public int minDepth(TreeNode root) {if (root == null) {return 0;}int left = minDepth(root.left);int right = minDepth(root.right);if (left == 0) {return right + 1;}if (right == 0) {return left + 1;}return Math.min(left, right) + 1;}

解题2：

层序遍历，这种效率是较高的

    public int minDepth(TreeNode root) {if (root == null) {return 0;}Queue<TreeNode> queue = new ArrayDeque<>();queue.offer(root);int level = 0;while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {TreeNode poll = queue.poll();if (poll.left != null) {queue.offer(poll.left);}if (poll.right != null) {queue.offer(poll.right);}// 这个就是叶子节点，只要遇到第一个叶子节点，就会返回值if (poll.left == null && poll.right == null) {return ++level;}}level++;}return level;}

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

解题思路：

很简单的一道递归调用，将节点的左右节点互相调换即可。

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

根据后缀表达式，构建一颗树。

    // 根据后缀表达式生成树public TreeNode constructExpressionTree(String[] token) {Stack<TreeNode> stack = new Stack<>();for (String s : token) {switch (s) {case "+", "-", "*", "/" -> {TreeNode right = stack.pop();TreeNode left = stack.pop();TreeNode parent = new TreeNode(s);parent.right = right;parent.left = left;stack.push(parent);}default -> {stack.push(new TreeNode(s));}}}return stack.peek();}

105 、从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

解题思路

preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

前序遍历，第一个节点肯定是头节点。确定头结点的值，可以在中序遍历中定位到头节点位置
中序数组中，头节点左侧是左子树，右侧是右子树
根据中序数组中判断出来的左右子树，可以在前序数组中分割出左右子树。
这样，就得到了根节点，左子树的前序和中序数组，右子树的前序和中序数组。就找到了递归的条件
递归结束条件，如果一个节点没有左右子树，说明前序数组和中序数组长度为0,。
public class Test105 {public TreeNode buildTree(int[] preorder, int[] inorder) {if (preorder.length == 0 || inorder.length == 0) {return null;}int rootValue = preorder[0];TreeNode root = new TreeNode(rootValue);for (int i = 0; i < inorder.length; i++) {// 找到中序数组中的根节点位置，左边是左子树，右边是右子树if (rootValue == inorder[i]) {// 中序数组，划分成左右两边int[] inLeft = Arrays.copyOfRange(inorder, 0, i);int[] inRight = Arrays.copyOfRange(inorder, i + 1, inorder.length);// 前序数组，也划分成左右两边int[] preLeft = Arrays.copyOfRange(preorder, 1, i + 1);int[] preRight = Arrays.copyOfRange(preorder, i + 1, inorder.length);//递归调用root.left = buildTree(preLeft, inLeft);root.right = buildTree(preRight, inRight);break;}}return root;}
}

106、从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

解题思路，和105题一样

    public TreeNode buildTree1(int[] inorder, int[] postorder) {if (postorder.length == 0 || inorder.length == 0) {return null;}int length = postorder.length;int rootValue = postorder[length-1];TreeNode root = new TreeNode(rootValue);for (int i = 0; i < length; i++) {// 找到中序数组中的根节点位置，左边是左子树，右边是右子树if (rootValue == inorder[i]) {// 中序数组，划分成左右两边int[] inLeft = Arrays.copyOfRange(inorder, 0, i);int[] inRight = Arrays.copyOfRange(inorder, i + 1, inorder.length);// 后序数组，也划分成左右两边int[] postLeft = Arrays.copyOfRange(postorder, 0, i );int[] postRight = Arrays.copyOfRange(postorder, i , inorder.length-1);//递归调用root.left = buildTree(inLeft,postLeft);root.right = buildTree(inRight,postRight);break;}}return root;}

3、二叉搜索树

给树的节点定义一个key，是不可用重复的。

二叉搜索树满足：节点的key大于左子树的key，小于右子树的key。

二叉搜索树的实现：

1、先定义二叉查找树的节点

二叉查找树节点static class BSTTreeNode {int key;Object value;BSTTreeNode left;BSTTreeNode right;public BSTTreeNode(int key) {this.key = key;}}

2、定义二叉查找树的方法

二叉查找树方法
public class BSTTree {// 根节点BSTTreeNode root;// 根据key，获取valuepublic Object get(int key) {return doGet(root, key);}// 获得树中最小key关联的值public Object min() {return null;}// 获得树中最大key关联的值public Object max() {return null;}// 找到一个key的前驱（就是比他key小的最大的值）public Object successor(int key) {return null;}// 找到一个key的后继（就是比他key大的最小的值）public Object predecessor(int key) {return null;}// 根据key删除节点public Object delete(int key) {return null;}public void put(int key, Object value) {}
}

3、get方法的实现

循环或者递归，比较key的值，key比当前节点的key大，就往右子树找，key比当前节点的key小，就往左子树找，找不到就返回null。

递归// 根据key，获取valuepublic Object get(int key) {return doGet(root, key);}private Object doGet(BSTTreeNode node, int key) {if (node == null) {return null;}if (node.key < key) {return doGet(node.right, key);// 向右找} else if (node.key > key) {return doGet(node.left, key); // 向左找} else {return node.value; // 找到了}}非递归public Object get1(int key) {BSTTreeNode node = root;while (node != null) {if (node.key > key) {node = node.left;} else if (node.key < key) {node = node.right;} else {return node;}}return null;}

4.min方法的实现：沿着根节点，一直往左找

    // 获得树中最小key关联的值public Object min() {return min(root);}public Object min(BSTTreeNode bstTreeNode) {BSTTreeNode node = bstTreeNode;while (true) {if (node == null) {return node;} else {node = node.left;}}}

5、max方法的实现：沿着根节点，一直往右找

// 获得树中最大key关联的值public Object max() {return max(root);}public Object max(BSTTreeNode bstTreeNode) {BSTTreeNode node = bstTreeNode;while (true) {if (node == null) {return node;} else {node = node.right;}}}

6、增加节点方法实现

分为两种，key已经存在了，就更新value，key不存在，就新增节点到树里面。
判断key是否存在，也要用到查找逻辑，可以在get的基础上进行修改。
首先，如果树是空的，那么直接创建节点赋值给root
查找树中的key，比较大小，往左或者往右进行查找
如果查找到了，就直接修改value的值。
如果找不到，说明需要新增，新增在那个节点下面呢？因此要定义一个临时变量，记录4步骤中查到的最后一个不为null的节点。
得到6中的节点，判断key的值，选择插入这个节点的左边还是右边。

    // key存在，更新，key不存在，新增public void put(int key, Object value) {BSTTreeNode add = new BSTTreeNode(key, value);BSTTreeNode node = root;if (root == null) {root = add;}BSTTreeNode parent = null;while (node != null) {parent = node; // parent 记录循环中的最后一个节点if (node.key > key) {node = node.left;} else if (node.key < key) {node = node.right;} else {// 找到了，更新操作node.value = value;return;}}// 没有找到，新增if (parent.key > key) {parent.left = add;} else {parent.right = add;}}

7、删除一个节点

删除节点没有左孩子，将右孩子给parent
删除节点没有右孩子，将左孩子给parent
删除节点没有左右孩子，已经被1,2两个场景包括了
删除节点左右孩子都有：
首先找到被删除节点的后继节点（其实就是去右子树中一直往左找到的最后一个）
如果找到的后继节点与要删除的节点相邻，说明这个后继节点没有左节点，可以直接把这个后继节点顶上
如果不相邻，把这个后继节点的右孩子顶到后继节点的位置（后继节点不可能有左孩子），然后把后继节点取代被删除节点就可以。

    // 根据key删除节点public Object delete(int key) {BSTTreeNode node = root;BSTTreeNode parent = null;while (node != null) {if (key < node.key) {parent = node;node = node.left;} else if (key > node.key) {parent = node;node = node.right;} else {// node就是当前节点，就不需要给parent赋值了break;}}if (node == null) {// 没找到这个节点return null;}// 删除操作if (node.left == null) {// 没有左孩子，那么就把右孩子顶上去shift(parent, node, node.right);} else if (node.right == null) {// 没有右孩子，那么就把左孩子顶上去shift(parent, node, node.left);} else {// 左右孩子都有// 先找后继节点，后继节点肯定是去右子树中去寻找的BSTTreeNode preNode = node.right;BSTTreeNode preParent = node;// 后继节点肯定就是一直向左找的哪个节点。while (preNode.left != null) {preParent = preNode;preNode = preNode.left;}// 如果后继节点和待删除节点不相邻,说明preParent发生了变化if (preParent != node) {// 先处理后继节点的后事 // --- 其实就是把后继节点的右孩子，提升，因为后继节点不可能有左孩子shift(preParent, preNode, preNode.right);preNode.right = node.right;}// 后继节点取代被删除节点shift(parent, node, preNode);preNode.left = node.left;}return node.value;}

8、找到一个节点的先驱节点

如果一个节点有左子树，那么这个节点就是左子树中最大的哪个节点
如果一个节点没有左子树
这个节点就是他自左边来的最近的祖先节点（3的是2,5的是4）
如果没有自左边来的最近的祖先节点，那么没有这个节点（1没有）

    // 找到一个key的前驱（就是比他key小的最大的值）public Object successor(int key) {BSTTreeNode node = root;BSTTreeNode ancestorFromLeft = null; // 记录从左而来的祖先节点while (node != null) {if (key < node.key) {node = node.left;} else if (key > node.key) {// 往右边查找，说明这个祖先节点是从左边来的ancestorFromLeft = node;node = node.right;} else {break;}}if (node == null) {return null; //没找到}if (node.left != null) {//存在左子树，那么就返回左子树中最大的一个值return max(node.left);}// 不存在左子树，那么就找左边来的祖先节点，距离自己最近的一个// 因为ancestorFromLeft每次都在更新，所以当前的ancestorFromLeft就是目标值。return ancestorFromLeft == null ? null : ancestorFromLeft.value;}

9、找到一个节点的后继节点 --- 与8是对称的

节点有右子树，那么节点就是右子树中的最小值
节点没有右子树：
这个节点就是他右边来的祖先的最近一个

    // 找到一个key的后继（就是比他key大的最小的值）public Object predecessor(int key) {BSTTreeNode node = root;BSTTreeNode ancestorFromRight = null;while (node != null) {if (key < node.key) {// 往左边查找，说明这个祖先节点是从右边来的ancestorFromRight = node;node = node.left;} else if (key > node.key) {node = node.right;} else {break;}}if (node == null) {return null; //没找到}if (node.right != null) {return min(node.right);}return ancestorFromRight == null ? null : ancestorFromRight.value;}

练习题：

LeetCode 450,700,701三题就对应了二叉查找树的增删查。对于删除操作，比较复杂要多加练习。

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

解题思路：

节点比左孩子大，比右孩子小（不包含等于的情况）
节点比左子树中最大的值大，比右子树中最小的值小 --- （1就可以合并到2中）
根据2的条件，递归

public class Test98 {public boolean isValidBST(TreeNode root) {return dsf(root);}// 递归方法public boolean dsf(TreeNode node) {// 节点是空，或者节点是叶子节点，符合二叉搜索树，可以返回trueif (node == null || (node.left == null && node.right == null)) {return true;}int val = node.val;// 定义一个临时变量TreeNode tmp = node;// 到左子树中找最大的值，要求比当前节点值小，否则返回falseif (tmp.left != null) {tmp = tmp.left;while (tmp.right != null) {tmp = tmp.right;}if (tmp.val >= val) {return false;}}// 到右子树中找最小的值，要求比当前节点值大，否则返回falsetmp = node;if (node.right != null) {tmp = tmp.right;while (tmp.left != null) {tmp = tmp.left;}if (tmp.val <= val) {return false;}}// 递归调用return dsf(node.left) && dsf(node.right);}
}

938. 二叉搜索树的范围和

给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。

----- 这一题，总的来说还是DSF更好理解，效率更好

解题思路：

深度优先遍历，因为是二叉查找树，因此树的节点是有顺序的。
如果当前节点比high大，那么只要在左子树中遍历就可以了
如果当前节点比low小，那么只要在右子树找那个遍历就可以了
否则，值就是当前节点的值加上左子树、右子树中符合要求的节点的和。
class Solution {public int rangeSumBST(TreeNode root, int low, int high) {if (root == null) {return 0;}if (root.val > high) {return rangeSumBST(root.left, low, high);}if (root.val < low) {return rangeSumBST(root.right, low, high);}return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);}
}

解题思路2：

广度优先遍历，同样利用二叉查找树的特性可以进行剪枝
实现思路和DSF一样，只不过是变成了BSF
注意一点：
ArrayDeque是能插入null作为节点的
LinkedList可以插入null作为节点
class Solution {public int rangeSumBST(TreeNode root, int low, int high) {if (root == null) {return 0;}int res = 0;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {TreeNode poll = queue.poll();if (poll == null) {continue;}if (poll.val > high) {queue.offer(poll.left);} else if (poll.val < low) {queue.offer(poll.right);} else {res += poll.val;queue.offer(poll.left);queue.offer(poll.right);}}}return res;}
}

1008. 前序遍历构造二叉搜索树

解题思路：

前序遍历，第一个值就是根节点，知道了根节点，遍历数组，一个个去插入节点即可。

class Solution {public TreeNode bstFromPreorder(int[] preorder) {if (preorder.length == 0) {return null;}TreeNode root = new TreeNode(preorder[0]);for (int i = 1; i < preorder.length; i++) {put(new TreeNode(preorder[i]), root);}return root;}public void put(TreeNode add, TreeNode node) {if (add == null) {return;}TreeNode preNode = null;while (node != null) {preNode = node;if (node.val > add.val) {node = node.left;} else if (node.val < add.val) {node = node.right;} else {break;}}if (preNode.val > add.val) {preNode.left = add;return;}if (preNode.val < add.val) {preNode.right = add;return;}}
}

235. 二叉搜索树的最近公共祖先

解题思路：

因为是二叉搜索树，因此最近的公共祖先-----转化为，找到最近的一个节点，p 和 q在这个节点的左右两边
注意，p或者q也可以是公共祖先

递归写法

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null) {return null;}TreeNode node = root;TreeNode min = p.val > q.val ? q : p;TreeNode max = p.val > q.val ? p : q;if (node.val >= min.val && node.val <= max.val) {return node;}if (node.val > max.val) {return lowestCommonAncestor(node.left, p, q);} else {return lowestCommonAncestor(node.right, p, q);}}
}

非递归写法

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {TreeNode node = root;TreeNode min = p.val > q.val ? q : p;TreeNode max = p.val > q.val ? p : q;while (true) {if (node.val >= min.val && node.val <= max.val) {return node;} else if (node.val > max.val) {node = node.left;} else {node = node.right;}}}
}