2023年6月22日发(作者：)

数据结构-⼆叉树-⾯试中常见的⼆叉树算法题数据结构 - ⼆叉树 - ⾯试中常见的⼆叉树算法题数据结构是⾯试中必定考查的知识点，⾯试者需要掌握⼏种经典的数据结构：线性表（数组、链表）、栈与队列、树（⼆叉树、⼆叉查找树、平衡⼆叉树、红⿊树）、图。本⽂主要介绍树中的常见的⼆叉树数据结构。包括概念简介⼆叉树中树节点的数据结构（Java）⼆叉树的遍历（Java）常见的⼆叉树算法题（Java）概念简介如果对⼆叉树概念已经基本掌握，可以跳过该部分，直接查看常见链表算法题。⼆叉树基本概念⼆叉树在图论中是这样定义的：⼆叉树是⼀个连通的⽆环图，并且每⼀个顶点的度不⼤于3。有根⼆叉树还要满⾜根结点的度不⼤于2。有了根结点之后，每个顶点定义了唯⼀的⽗结点，和最多2个⼦结点。⼆叉树性质如下：⼆叉树的每个结点⾄多只有⼆棵⼦树(不存在度⼤于2的结点)，⼆叉树的⼦树有左右之分，次序不能颠倒。⼆叉树的第 i 层⾄多有 个结点。深度为 k 的⼆叉树⾄多有 个结点。对任何⼀棵⼆叉树T，如果其终端结点数为，度为2的结点数为，则。⼀棵深度为k，且有 个节点称之为满⼆叉树；深度为k，有n个节点的⼆叉树，当且仅当其每⼀个节点都与深度为k的满⼆叉树中，序号为1⾄n的节点对应时，称之为完全⼆叉树。平衡⼆叉树⼜被称为AVL树（区别于AVL算法），它是⼀棵⼆叉排序树，且具有以下性质：它是⼀棵空树或它的左右两个⼦树的⾼度差的绝对值不超过1，并且左右两个⼦树都是⼀棵平衡⼆叉树。⼆叉树中树节点的数据结构⼆叉树由⼀系列树结点组成，每个结点包括三个部分：⼀个是存储数据元素的数据域，另⼀个是存储左⼦结点地址的指针域，另⼀个是存储右⼦结点地址的指针域。定义树节点为类：TreeNode。具体实现如下：public class TreeNode { public int val; // 数据域 public TreeNode left; // 左⼦树根节点 public TreeNode right; // 右⼦树根节点 public TreeNode() { } public TreeNode(int val) { = val; }}⼆叉树的遍历1. 前序遍历递归解法：如果⼆叉树为空，空操作如果⼆叉树不为空，访问根节点，前序遍历左⼦树，前序遍历右⼦树/** * 1. 前序遍历 * 递归 * @param root 树根节点 */public static void preorderTraversalRec(TreeNode root){ if (root == null) { return; } ( + "->"); preorderTraversalRec(); preorderTraversalRec();}⾮递归解法：⽤⼀个辅助stack，总是先把右孩⼦放进栈。/** * 1. 前序遍历 * ⾮递归 * @param root 树根节点 */public static void preorderTraversal2(TreeNode root) { if (root == null) { return; } Stack stack = new Stack<>(); // 辅助栈 TreeNode cur = root; while (cur != null || !y()) { while (cur != null) { // 不断将左⼦节点⼊栈，直到cur为空 (cur); ( + "->"); // 前序遍历，先打印当前节点在打印左⼦节点，然后再把右⼦节点加到栈中 cur = ; } if (!y()) { // 栈不为空，弹出栈元素 cur = (); // 此时弹出最左边的节点 cur = ; // 令当前节点为右⼦节点 } }}/** * 1. 前序遍历 * ⾮递归解法2 * @param root 树根节点 */public static void preorderTraversal(TreeNode root) { if (root == null) { return; } Stack stack = new Stack<>(); // 辅助栈保存树节点 (root); while (!y()) { // 栈不为空 TreeNode temp = (); ( + "->"); // 先根节点，因为是前序遍历 if ( != null) { // 先添加右孩⼦，因为栈是先进后出 (); } if ( != null) { (); } }}2. 中序遍历递归解法：如果⼆叉树为空，空操作如果⼆叉树不为空，中序遍历左⼦树，访问根节点，中序遍历右⼦树/** * 2. 中序遍历 * 递归 * @param root 树根节点 */public static void inorderTraversalRec(TreeNode root){ if (root == null) { return; } inorderTraversalRec(); ( + "->"); inorderTraversalRec();}⾮递归解法：⽤栈先把根节点的所有左孩⼦都添加到栈内，然后输出栈顶元素，再处理栈顶元素的右⼦树。/** * 2. 中序遍历 * ⾮递归 * @param root 树根节点 */public static void inorderTraversal(TreeNode root) { if (root == null) { return; } Stack stack = new Stack<>(); // 辅助栈 TreeNode cur = root; while (cur != null || !y()) { while (cur != null) { // 不断将左⼦节点⼊栈，直到cur为空 (cur); cur = ; } if (!y()) { // 栈不为空，弹出栈元素 cur = (); // 此时弹出最左边的节点 ( + "->"); // 中序遍历，先打印左⼦节点在打印当前节点，然后再把右⼦节点加到栈中 cur = ; // 令当前节点为右⼦节点 } }}3. 后序遍历递归解法：如果⼆叉树为空，空操作如果⼆叉树不为空，后序遍历左⼦树，后序遍历右⼦树，访问根节点/** * 3. 后序遍历 * 递归 * @param root 树根节点 */public static void postorderTraversalRec(TreeNode root){ if (root == null) { return; } postorderTraversalRec(); postorderTraversalRec(); ( + "->");}⾮递归解法：双栈法。/** * 3. 后序遍历 * ⾮递归 * @param root 树根节点 */public static void postorderTraversal(TreeNode root) { if(root == null) { return; } Stack stack1 = new Stack<>(); // 保存树节点 Stack stack2 = new Stack<>(); // 保存后序遍历的结果 (root); while (!y()) { TreeNode temp = (); (temp); // 将弹出的元素加到stack2中 if ( != null) { // 左⼦节点先⼊栈 (); } if ( != null) { // 右⼦节点后⼊栈 (); } } while (!y()) { (().val + "->"); }}4. 层次遍历思路：分层遍历⼆叉树（按层次从上到下，从左到右）迭代，相当于⼴度优先搜索，使⽤队列实现。队列初始化，将根节点压⼊队列。当队列不为空，进⾏如下操作：弹出⼀个节点，访问，若左⼦节点或右⼦节点不为空，将其压⼊队列。/** * 4. 层次遍历 * @param root 根节点 */public static void levelTraversal(TreeNode root){ if(root == null) { return; } Queue queue = new LinkedList<>(); // 对列保存树节点 (root); while (!y()) { TreeNode temp = (); ( + "->"); if ( != null) { // 添加左右⼦节点到对列 (); } if ( != null) { (); } }}常见的⼆叉树算法题1. 求⼆叉树中的节点个数递归解法： O(n)如果⼆叉树为空，节点个数为0如果⼆叉树不为空，⼆叉树节点个数 = 左⼦树节点个数 + 右⼦树节点个数 + 1/** * 1. 求⼆叉树中的节点个数 * 递归 * @param root 树根节点 * @return 节点个数 */public static int getNodeNumRec(TreeNode root) { if (root == null) { return 0; } return getNodeNumRec() + getNodeNumRec() + 1;}⾮递归解法：O(n)。基本思想同LevelOrderTraversal。即⽤⼀个Queue，在Java⾥⾯可以⽤LinkedList来模拟。/** * 1. 求⼆叉树中的节点个数 * ⾮递归 * @param root 树根节点 * @return 节点个数 */public static int getNodeNum(TreeNode root) { if (root == null) { return 0; } Queue queue = new LinkedList<>(); // ⽤队列保存树节点，先进先出 (root); int count = 1; // 节点数量 while (!y()) { TreeNode temp = (); // 每次从对列中删除节点，并返回该节点信息 if ( != null) { // 添加左⼦孩⼦到对列 (); count++; } if ( != null) { // 添加右⼦孩⼦到对列 (); count++; } } return count;}2. 求⼆叉树的深度（⾼度）递归解法： O(n)如果⼆叉树为空，⼆叉树的深度为0如果⼆叉树不为空，⼆叉树的深度 = max(左⼦树深度， 右⼦树深度) + 1/*** 求⼆叉树的深度（⾼度）

* 递归* @return 树的深度*/public static int getDepthRec(TreeNode root) { if (root == null) { return 0; } return (getDepthRec(), getDepthRec()) + 1;}⾮递归解法：O(n)。基本思想同LevelOrderTraversal。即⽤⼀个Queue，在Java⾥⾯可以⽤LinkedList来模拟。/** * 求⼆叉树的深度（⾼度） * ⾮递归 * @param root 树根节点 * @return 树的深度 */public static int getDepth(TreeNode root) { if (root == null) { return 0; } int currentLevelCount = 1; // 当前层的节点数量 int nextLevelCount = 0; // 下⼀层节点数量 int depth = 0; // 树的深度 Queue queue = new LinkedList<>(); // 对列保存树节点 (root); while (!y()) { TreeNode temp = (); // 移除节点 currentLevelCount--; // 当前层节点数减1 if ( != null) { // 添加左节点并更新下⼀层节点个数 (); nextLevelCount++; } if ( != null) { // 添加右节点并更新下⼀层节点个数 (); nextLevelCount++; } if (currentLevelCount == 0) { // 如果是该层的最后⼀个节点，树的深度加1 depth++; currentLevelCount = nextLevelCount; // 更新当前层节点数量并且重置下⼀层节点数量 nextLevelCount = 0; } } return depth;}3. 求⼆叉树第k层的节点个数递归解法： O(n)思路：求以root为根的k层节点数⽬，等价于求以root左孩⼦为根的k-1层（因为少了root）节点数⽬ 加上以root右孩⼦为根的k-1层（因为 少了root）节点数⽬。即：如果⼆叉树为空或者k<1，返回0如果⼆叉树不为空并且k==1，返回1如果⼆叉树不为空且k>1，返回root左⼦树中k-1层的节点个数与root右⼦树k-1层节点个数之和/** * 求⼆叉树第k层的节点个数 * 递归 * @param root 根节点 * @param k 第k个节点 * @return 第k层节点数 */public static int getNodeNumKthLevelRec(TreeNode root, int k) { if (root == null || k < 1) { return 0; } if (k == 1) { return 1; } return getNodeNumKthLevelRec(, k - 1) + getNodeNumKthLevelRec(, k - 1);}4. 求⼆叉树中叶⼦节点的个数递归解法：如果⼆叉树为空，返回0如果⼆叉树是叶⼦节点，返回1如果⼆叉树不是叶⼦节点，⼆叉树的叶⼦节点数 = 左⼦树叶⼦节点数 + 右⼦树叶⼦节点数/** * 4. 求⼆叉树中叶⼦节点的个数 * 递归 * @param root 根节点 * @return 叶⼦节点个数 */public static int getNodeNumLeafRec(TreeNode root) { if (root == null) { return 0; } if ( == null && == null) { return 1; } return getNodeNumLeafRec() + getNodeNumLeafRec();}⾮递归解法：基于层次遍历进⾏求解，利⽤Queue进⾏。 /** * 4. 求⼆叉树中叶⼦节点的个数（迭代） * ⾮递归 * @param root 根节点 * @return 叶⼦节点个数 */public static int getNodeNumLeaf(TreeNode root){ if (root == null) { return 0; } int leaf = 0; // 叶⼦节点个数 Queue queue = new LinkedList<>(); (root); while (!y()) { TreeNode temp = (); if ( == null && == null) { // 叶⼦节点 leaf++; } if ( != null) { (); } if ( != null) { (); } } return leaf;}5. 判断两棵⼆叉树是否相同的树递归解法：如果两棵⼆叉树都为空，返回真如果两棵⼆叉树⼀棵为空，另外⼀棵不为空，返回假如果两棵⼆叉树都不为空，如果对应的左⼦树和右⼦树都同构返回真，其他返回假/** * 5. 判断两棵⼆叉树是否相同的树。 * 递归 * @param r1 ⼆叉树1 * @param r2 ⼆叉树2 * @return 是否相同 */public static boolean isSameRec(TreeNode r1, TreeNode r2) { if (r1 == null && r2 == null) { // 都是空 return true; } else if (r1 == null || r2 == null) { // 有⼀个为空，⼀个不为空 return false; } if ( != ) { // 两个不为空，但是值不相同 return false; } return isSameRec(, ) && isSameRec(, ); // 递归遍历左右⼦节点}⾮递归解法：利⽤Stack对两棵树对应位置上的节点进⾏判断是否相同。/** * 5. 判断两棵⼆叉树是否相同的树（迭代） * ⾮递归 * @param r1 ⼆叉树1 * @param r2 ⼆叉树2 * @return 是否相同 */public static boolean isSame(TreeNode r1, TreeNode r2){ if (r1 == null && r2 == null) { // 都是空 return true; } else if (r1 == null || r2 == null) { // 有⼀个为空，⼀个不为空 return false; } Stack stack1 = new Stack<>(); Stack stack2 = new Stack<>(); (r1); (r2); while (!y() && !y()) { TreeNode temp1 = (); TreeNode temp2 = (); if (temp1 == null && temp2 == null) { // 两个元素都为空，因为添加的时候没有对空节点做判断 continue; } else if (temp1 != null && temp2 != null && == ) { (); // 相等则添加左右⼦节点判断 (); (); (); } else { return false; } } return true;}6. 判断⼆叉树是不是平衡⼆叉树递归实现：借助前⾯实现好的求⼆叉树⾼度的函数如果⼆叉树为空， 返回真如果⼆叉树不为空，如果左⼦树和右⼦树都是AVL树并且左⼦树和右⼦树⾼度相差不⼤于1，返回真，其他返回假/** * 6. 判断⼆叉树是不是平衡⼆叉树 * 递归 * @param root 根节点 * @return 是否⼆叉平衡树（AVL树） */public static boolean isAVLTree(TreeNode root) { if (root == null) { return true; } if ((getDepth() - getDepth()) > 1) { // 左右⼦树⾼度差⼤于1 return false; } return isAVLTree() && isAVLTree(); // 递归判断左右⼦树}7. 求⼆叉树的镜像递归实现：破坏原来的树，把原来的树改成其镜像如果⼆叉树为空，返回空如果⼆叉树不为空，求左⼦树和右⼦树的镜像，然后交换左右⼦树/** * 7. 求⼆叉树的镜像 * 递归 * @param root 根节点 * @return 镜像⼆叉树的根节点 */public static TreeNode mirrorRec(TreeNode root) { if (root == null) { return root; } TreeNode left = mirrorRec(); // 递归镜像左右⼦树 TreeNode right = mirrorRec(); = left; // 更新根节点的左右⼦树为镜像后的树 = right; return root;}递归实现：不能破坏原来的树，返回⼀个新的镜像树如果⼆叉树为空，返回空如果⼆叉树不为空，求左⼦树和右⼦树的镜像，然后交换左右⼦树/** * 7. 求⼆叉树的镜像 * 递归 * @param root 根节点 * @return 镜像⼆叉树的根节点 */public static TreeNode mirrorCopyRec(TreeNode root) { if (root == null) { return root; } TreeNode newRoot = new TreeNode(); // 创建新节点，然后交换左右⼦树 = mirrorCopyRec(); = mirrorCopyRec(); return newRoot;}⾮递归实现：破坏原来的树，把原来的树改成其镜像/** * 7. 求⼆叉树的镜像 * ⾮递归 * @param root 根节点 * @return 镜像⼆叉树的根节点 */public static void mirror(TreeNode root) { if (root == null) { return ; } Stack stack = new Stack<>(); (root); while (!y()){ TreeNode cur = (); // 交换左右孩⼦ TreeNode tmp = ; = ; = tmp; if( != null) { (); } if ( != null) { (); } }}⾮递归实现：不能破坏原来的树，返回⼀个新的镜像树/** * 7. 求⼆叉树的镜像 * ⾮递归 * @param root 根节点 * @return 镜像⼆叉树的根节点 */public static TreeNode mirrorCopy(TreeNode root) { if (root == null) { return null; } Stack stack = new Stack(); Stack newStack = new Stack(); (root); TreeNode newRoot = new TreeNode(); (newRoot); while (!y()) { TreeNode cur = (); TreeNode newCur = (); if ( != null) { (); = new TreeNode(); (); } if ( != null) { (); = new TreeNode(); (); } } return newRoot;}8. 判断两个⼆叉树是否互相镜像递归解法：与⽐较两棵⼆叉树是否相同解法⼀致（题5），⾮递归解法省略。⽐较r1的左⼦树的镜像是不是r2的右⼦树⽐较r1的右⼦树的镜像是不是r2的左⼦树/** * 8. 判断两个树是否互相镜像 * @param r1 ⼆叉树 1 * @param r2 ⼆叉树 2 * @return 是否互相镜像 */public static boolean isMirrorRec(TreeNode r1, TreeNode r2) { if (r1 == null && r2 == null) { return true; } else if (r1 == null || r2 == null) { return false; } if ( != ) { return false; } // 递归⽐较r1的左⼦树的镜像是不是r2右⼦树 // 和r1的右⼦树的镜像是不是r2的左⼦树 return isMirrorRec(, ) && isMirrorRec(, );}9. 求⼆叉树中两个节点的最低公共祖先节点递归解法：如果两个节点分别在根节点的左⼦树和右⼦树，则返回根节点如果两个节点都在左⼦树，则递归处理左⼦树；如果两个节点都在右⼦树，则递归处理右⼦树/** * 9. 求⼆叉树中两个节点的最低公共祖先节点 * 递归 * @param root 树根节点 * @param n1 第⼀个节点 * @param n2 第⼆个节点 * @return 最低公共祖先节点 */public static TreeNode getLastCommonParentRec(TreeNode root, TreeNode n1, TreeNode n2) { if (findNodeRec(, n1)) { // 如果n1在左⼦树 if (findNodeRec(, n2)) { // 如果n2在右⼦树 return root; // 返回根节点 } else { // 如果n2也在左⼦树 return getLastCommonParentRec(, n1, n2); // 递归处理 } } else { // 如果n1在右⼦树 if (findNodeRec(, n2)) { // 如果n2在左⼦树 return root; // 返回根节点 } else { // 如果n2在右⼦树 return getLastCommonParentRec(, n1, n2); // 递归处理 } }}/** * 递归判断⼀个点是否在树⾥ * @param root 根节点 * @param node 查找的节点 * @return 是否找到该节点 * @return 是否找到该节点 */private static boolean findNodeRec(TreeNode root, TreeNode node) { if (node == null || root == null) { return false; } if (root == node) { return true; } // 先尝试在左⼦树中查找 boolean found = findNodeRec(, node); if (!found) { // 如果查找不到，再在右⼦树中查找 found = findNodeRec(, node); } return found;}/** * 9. 树中两个节点的最低公共祖先节点 * 递归解法2（更简单） * @param root 树根节点 * @param n1 第⼀个节点 * @param n2 第⼆个节点 * @return 最低公共祖先节点 */public static TreeNode getLastCommonParentRec2(TreeNode root, TreeNode n1, TreeNode n2) { if (root == null) { return null; } // 如果有⼀个match，则说明当前node就是要找的最低公共祖先 if ((n1) || (n2)) { return root; } TreeNode commonLeft = getLastCommonParentRec2(, n1, n2); TreeNode commonRight = getLastCommonParentRec2(, n1, n2); // 如果⼀个在左⼦树找到，⼀个在右⼦树找到，则说明root是唯⼀可能得最低公共祖先 if (commonLeft != null && commonRight != null) { return root; } // 其他情况是要不然在左⼦树要不然在右⼦树 if (commonLeft != null) { return commonLeft; } return commonRight;}⾮递归算法：得到从⼆叉树根节点到两个节点的路径，路径从头开始的最后⼀个公共节点就是它们的最低公共祖先节点/** * 9. 树中两个节点的最低公共祖先节点 * ⾮递归 * @param root 树根节点 * @param n1 第⼀个节点 * @param n2 第⼆个节点 * @return 第⼀个公共祖先节点 */public static TreeNode getLastCommonParent(TreeNode root, TreeNode n1, TreeNode n2) { if (root == null || n1 == null || n2 == null) { return null; } ArrayList p1 = new ArrayList<>(); boolean res1 = getNodePath(root, n1, p1); ArrayList p2 = new ArrayList<>(); boolean res2 = getNodePath(root, n2, p2); if (!res1 || !res2) { return null; } TreeNode last = null; Iterator iter1 = or(); Iterator iter2 = or(); while (t() && t()) { TreeNode tmp1 = (); TreeNode tmp2 = (); if (tmp1 == tmp2) { last = tmp1; } else { // 直到遇到⾮公共节点 break; } } return last;}/** * 把从根节点到node路径上所有的点都添加到path中 * @param root 树根节点 * @param node 终点节点 * @param path 路径 * @return 是否是⽬标节点 */public static boolean getNodePath(TreeNode root, TreeNode node, ArrayList path) { if (root == null) { return false; } (root); // 把这个节点添加到路径中 if (root == node) { return true; } boolean found = false; found = getNodePath(, node, path); // 先在左⼦树中找 if (!found) { found = getNodePath(, node, path); } if (!found) { // 如果实在没找到证明这个节点不在路径中，删除刚刚那个节点 (root); } return found;}10. 判断是否为⼆分查找树BST递归解法：中序遍历的结果应该是递增的。/** * 10. 判断是否为⼆分查找树BST * @param root 根节点 * @param pre 上⼀个保存的节点 * @return 是否为BST树 */public static boolean isValidBST(TreeNode root, int pre){ if (root == null) { return true; } boolean left = isValidBST(, pre); if (!left) { return false; } if( <= pre) { return false; } pre = ; boolean right = isValidBST(, pre); if(!right) { return false; } return true;}⾮递归解法：参考⾮递归中序遍历。/**

* 10. 判断是否为⼆分查找树BST * ⾮递归 * @param root 根节点 */public boolean isValidBST2(TreeNode root){ Stack stack = new Stack<>(); //设置前驱节点 TreeNode pre = null; while(root != null || !y()){ while (root != null) { // 将当前节点，以及左⼦树⼀直⼊栈，循环结束时，root==null (root); root = ; } root = (); //⽐较并更新前驱，与普通遍历的区别就在下⾯四⾏ if(pre != null && <= ){ return false; } pre = root; root = ; //访问右⼦树 } return true;}