目录性质树结构二叉树​编辑 ​编辑结构遍历迭代中序层次遍历bfs二叉树的层次遍历习题二叉树中节点最多的层的节点数二叉查找树BST结构判断二叉查找树BST类里的方法添加删除搜索创建最大值最小值contains某节点的后继带parent不带parent某节点的前驱某节点高度平衡二叉树AVL平衡因子添加删除调整平衡右旋和左旋带parent的AVL叶子节点的个数第k层的节点数是否是完全二叉树是否相同是否镜像翻转二叉树二叉树的镜像前序遍历后序遍历中序遍历非递归BST区间搜索利用bfs实现利用dfs实现二叉树套路判断平衡二叉树判断完全二叉树性质树上面的性质因为两个结点由一条边连成结点数目越多算法复杂度越高结构二叉树结构与树的层次遍历思路一致只不过孩子列表明确成了左右孩子// 定义二叉树节点的类 class Node { int val; Node lchild; // 左子树 Node rchild; // 右子树 // 构造函数初始化节点的值和子树 Node(int val) { this.val val; this.lchild null; this.rchild null; } }遍历先序根左右中序左根右后序左右根以先序为例递归先序下图里面的1、2、3是第几次回到本节点从递归流程中看迭代先序1、从栈中弹出一个节点2、打印这个节点3、按先右后左如果有的顺序将节点压栈4、重复上面步骤直到全打印public static void pre(Node head) { // head是一棵树的头节点 if(head ! null) { StackNode stack new StackNode(); stack.add(head); while(!stack.isEmpty()) { // 1. Node currNode stack.pop(); // 2. System.out.print(currNode.val ); // 3. if(currNode.right ! null) { stack.push(currNode.right); } if(currNode.left ! null) { stack.push(currNode.left); } } } }迭代后序1、从栈中弹出一个节点2、把节点放入备用栈3、按先左后右如果有的顺序将节点压栈4、重复上面步骤直到全压入备用栈5、打印备用栈public static void posOrderUnRecur1(Node head) { System.out.print(pos-order: ); if (head ! null) { StackNode s1 new StackNode(); StackNode s2 new StackNode(); s1.push(head); while (!s1.isEmpty()) { head s1.pop(); s2.push(head); if (head.left ! null) { s1.push(head.left); } if (head.right ! null) { s1.push(head.right); } } while (!s2.isEmpty()) { System.out.print(s2.pop().value ); } } System.out.println(); }迭代中序1、每颗子树整棵树的左孩子全部进栈下面循环里的if代码2、弹出节点3、打印4、对其有孩子重复上面操作public static void inOrderUnRecur(Node head) { System.out.print(in-order: ); if (head ! null) { StackNode stack new StackNode(); while (!stack.isEmpty() || head ! null) { //不断将左孩子进栈移动指针 if (head ! null) { stack.push(head); head head.left; } else { //左孩子全进栈了开始弹出节点 head stack.pop(); //1、打印 System.out.print(head.value ); //2、将指针移到弹出节点的右孩子上用循环操作他有左孩子就进if没有就进else head head.right; } } } System.out.println(); }层次遍历bfs利用队列弹一个加N个队列里弹出一个元素就把这个元素的所有孩子加进去具体来说指针先指树根加入队列里后弹出队列把他的孩子都加入再弹再加关于树的很多题目都用到了这种遍历需要对每个结点做处理的但又不需要按某种路线比如一条路走到黑就用层序遍历即可二叉树的层次遍历与树的层次遍历思路一致只不过孩子列表明确成了左右孩子public void levelOrder(Node root) { if (root null) { return; } QueueNode contain new LinkedList(); contain.add(root); Node curr; // 队列不为空就一直处理 while (!contain.isEmpty()) { // 弹出一个 curr contain.poll(); System.out.println(curr.val ); // 添加其孩子 //先加左再加右 if (curr.left ! null) contain.add(curr.left); if (curr.right ! null) contain.add(curr.right); } }习题二叉树中节点最多的层的节点数在层序遍历的基础上添加代码来完成加个hashmap记录节点的所在层数每次向栈加新节点的同时向hashmap记录这个新节点的层数当前处理节点所在层数1将当前层数与当前处理节点所在层数做比较相等则该节点属于本层本层总结点数1不相等则该节点属于下一层结算本层数据去处理下一层public int maxNodesInLevel(Node head) { if (head null) { return 0; } QueueNode queue new LinkedList(); queue.add(head); //用hashmap记录节点的所在层数 HashMapNode, Integer levelMap new HashMap(); //头节点层数是1 levelMap.put(head, 1); //当前层数 int curLevel 1; //当前层数的结点数 int curLevelNodes 0; //最终所求 int max Integer.MIN_VALUE; while (!queue.isEmpty()) { //从栈中弹出节点 Node cur queue.poll(); //拿到当前处理节点的层数 int curNodeLevel levelMap.get(cur); //当前处理节点的层数 与 当前层数一致则该节点属于当前层 if (curNodeLevel curLevel) { //当前层数的结点数1 curLevelNodes; } else { //该节点属于下一层 //结算当前层数据 max Math.max(max, curLevelNodes); curLevel; //重置为1 curLevelNodes 1; } //当前处理节点的左右孩子节点的层数 是当前处理节点层数1 if (cur.left ! null) { levelMap.put(cur.left, curNodeLevel 1); queue.add(cur.left); } if (cur.right ! null) { levelMap.put(cur.right, curNodeLevel 1); queue.add(cur.right); } } // 检查最后一层 max Math.max(max, curLevelNodes); return max; }二叉查找树BST比root小的放左边大的放右边中序遍历左→根→右可得到严格递增的节点值序列这是判断二叉搜索树的重要依据结构与二叉树相同// 定义二叉搜索树的类 public class BST { private Node root; // 根节点 private int size; // 节点个数 // 构造函数初始化根节点为null public BST() { this.root null; this.size 0; } // 判断二叉搜索树是否为空 public boolean isEmpty() { return root null; } // 获取二叉搜索树的节点个数 public int size() { return size; } // 清空二叉搜索树 public void clear() { this.root null; } }判断二叉查找树中序遍历是升序的则是二叉查找树public static int preValue Integer.MIN_VALUE; public static boolean checkBST(Node head) { if (head null) { return true; } boolean isLeftBst checkBST(head.left); if (!isLeftBst) { return false; } if (head.value preValue) { return false; } else { preValue head.value; } return checkBST(head.right); }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; }删除需要考虑三种情况要删除的节点是叶子节点直接删除该节点。要删除的节点只有一个子节点用该子节点替换要删除的节点。要删除的节点有两个子节点找到该节点右子树中的最小节点即右子树中最左边的节点用这个最小节点的值替换要删除节点的值然后删除右子树中的最小节点。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); } }创建这里没有维护sizepublic 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; } Node node findMax(root); return node.val; } private Node findMax(Node root){ if(root.right null){ return root; } return findMax(root.right); }最小值最左边的值最小同上220-年龄 60-80// 找最小树的最左节点 public int Min(){ if (root null){ return 100000; } Node node findMin(root); return node.val; } private Node findMin(Node root){ if(root.left null){ return root; } return findMin(root.left); }containspublic 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、没有右子树则向上追溯直到某个祖先节点是左孩子那么这个祖先节点的父节点就是所求也就是后继节点是最后一个比目标节点值大的祖先节点带parentpublic static Node findSuccessor(Node node) { if (node null) { return null; } // 情况 1节点有右子树 if (node.right ! null) { return findMin(node.right); // 找到右子树中的最左节点 } // 情况 2节点没有右子树 Node current node; Node parent current.parent; while (parent ! null current parent.right) { current parent; parent parent.parent; } return parent; }不带parent思路一样只是不找第一个左孩子了而是用括号里的规则后继节点是最后一个比目标节点值大的祖先节点意思是如果按原来的思路向上回溯找第一个左孩子而如果从上到下找则找的是最后一个但不超过目标节点的那个节点如果超过目标节点了就不符合追溯第一个的思路了因为没有parent不能从下到上只能从上到下所以要传一个rootpublic static Node findSuccessor(Node root, Node target) { if (root null || target null) { return null; } // 情况 1目标节点有右子树 if (target.right ! null) { return findMin(target.right); // 找到右子树中的最左节点 } // 情况 2目标节点没有右子树 // successor是后继 Node successor null; Node curr root; // 一直找直到curr指向目标节点就停止也就是把目标节点上面的元素都处理一遍 while (curr ! null) { if (curr.val target.val) { successor curr; // 当前节点可能是后继节点 curr curr.left; // 继续向左子树查找更小的值 } else if (curr.val target.val) { curr curr.right; // 继续向右子树查找 } else { // curr指向目标节点停止 break; // 找到目标节点退出循环 } } return successor; }某节点的前驱指的是中序遍历后的那个序列某节点的前驱就是比这个节点小的第一个节点两种情况1、是其左子树的最大值2、没有左子树则向上追溯直到某个祖先节点是右孩子那么这个祖先节点的父节点就是所求这道题TreeNode带parent代码参考某节点的后继某节点高度当前节点到叶子节点的最长路径长度递归得到左右子树的高度取较高的一方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左右子树的高度差平衡因子不大于1AVL也是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 (nodenull){ return 0; } return node.height; } //获取当前节点的平衡因子 public int getBalanceFactor(Node node){ if (nodenull){ 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就是nully的左孩子就是null Node 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); }是否是完全二叉树利用层序遍历在此基础上对每次拿到的节点做处理层序遍历的每个节点①、左孩子为空右孩子不为空的情况则不是完全二叉树②、如果后面的节点都应该是叶子节点但是又有左孩子或右孩子则不是完全二叉树所以要维护一个变量用于表示是否后面的节点都应该是叶子节点思路借鉴原文链接https://blog.csdn.net/Hellowenpan/article/details/116700476public boolean isCompleteTree(Node root) { if (root null) { return true; } // 从当前节点开始后面的节点是否都需要是叶子节点 boolean isLeafNode false; QueueNode contain new LinkedList(); contain.add(root); Node curr; // 队列不为空就一直处理 while (!contain.isEmpty()) { // 弹出一个 curr contain.poll(); // ①、左孩子为空右孩子不为空的情况直接返回false if (curr.right ! null curr.left null) { return false; } // ②、如果后面的节点都应该是叶子节点但是又有左孩子或右孩子则直接返回false if (isLeafNode (curr.left ! null || curr.right ! null)) { return false; } // ③、遇到第一个左右孩子不双全的节点那么该节点后的所有节点都应该是叶子节点 if (curr.left null || curr.right null) { isLeafNode true; } // 压入左孩子到队列 if (curr.left ! null) { contain.add(curr.left); } // 压入右孩子到队列 if (curr.right ! null) { contain.add(curr.right); } } return true; }是否相同要判断两棵树是否相同必须同时满足以下两个条件结构相同两棵树的节点位置和父子关系必须一致。节点值相同对应位置的节点值必须相等。递归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) { // 使用栈来存储需要比较的节点对 StackNode[] 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; }注意中序遍历的结果不能唯一确定一棵树的结构因此不能直接用来判断两棵树是否相同反例但中序遍历搭配前序或者后序遍历即可唯一确定一棵树所以可以比较两种遍历的结果是否一致一致就相同但这样需要开辟空间存遍历结果所以这种方法不太好ListInteger存结果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 ); }中序遍历非递归利用栈用一个指针curr指向当前处理节点1、把左孩子全加进去然后开始出栈2、出一个节点就检查他有没有右孩子有就将curr指向右孩子重复1、2动作public static void inOrder(Node root) { Node curr root; StackNode contain new Stack(); while (curr ! null || !contain.isEmpty()) { // 把所有的左孩子都加入 while (curr ! null) { contain.push(curr); curr curr.left; } Node t contain.pop(); System.out.println(t.val); if (t.right ! null) { curr t.right; } } }BST区间搜索给定一个区间范围输出所有在这个区间的值利用bfs实现遍历到每一个节点判断在不在区间中public void IntervalSearch(Node root,int low,int high) { if (root null) { return; } QueueNode contain new LinkedList(); contain.add(root); Node curr; // 队列不为空就一直处理 while (!contain.isEmpty()) { // 弹出一个 curr contain.poll(); if (curr.val low curr.val high) System.out.println(curr.val ); // 添加其孩子 if (curr.left ! null) contain.add(curr.left); if (curr.right ! null) contain.add(curr.right); } }利用dfs实现分别处理左子树当前节点和右子树public void IntervalSearch(Node root, int low, int high) { // 递归终止条件如果当前节点为空直接返回 if (root null) { return; } // 找一个条件使程序需要遍历左子树 // 由于 // 如果当前节点的值大于 low左子树中才可能存在满足条件的节点递归遍历左子树 //如果low则左子树中不存在满足条件的节点不用遍历左子树 // 所以条件是root.val low if (root.val low) { IntervalSearch(root.left, low, high); } // 如果当前节点的值在 [low, high] 范围内则输出该节点的值 if (root.val low root.val high) { System.out.print(root.val ); } // 找一个条件使程序需要遍历右子树 // 剩余思路同上 if (root.val high) { IntervalSearch(root.right, low, high); } }二叉树套路向左孩子要信息向右孩子要信息进行处理信息如果不止一个直接封装成类如果要的信息不一样直接全封装成类求全集判断平衡二叉树左孩子是否是平衡二叉树高度是右孩子是否是平衡二叉树高度是//处理信息的 public static boolean isBalanced(Node head) { return process(head).isBalanced; } public static class ReturnType { public boolean isBalanced; public int height; public ReturnType(boolean isB, int hei) { isBalanced isB; height hei; } } //收集信息的 public static ReturnType process(Node x) { if (x null) { return new ReturnType(true, 0); } //得到左右孩子信息ReturnType ReturnType leftData process(x.left); ReturnType rightData process(x.right); //得到自己的信息ReturnType int height Math.max(leftData.height, rightData.height) 1; boolean isBalanced leftData.isBalanced rightData.isBalanced Math.abs(leftData.height - rightData.height) 2; return new ReturnType(isBalanced, height); }判断完全二叉树层序遍历检查左右孩子1、有右孩子没左孩子return false1满足时2、遇到第一个孩子不双全时接下来的节点都得是叶子节点没孩子