数据结构7-二叉树

发布时间：2026/10/22 7:25:34

文章目录一. 介绍1. 树的基本特性2. 应用场景二. 二叉树1. 二叉树的实现1.1 前(先)序遍历 - 递归实现1.1 前(先)序遍历 - 迭代实现1.2 中序遍历 - 递归实现1.2 中序遍历 - 迭代实现1.3 后序遍历 - 递归实现1.3 后序遍历 - 迭代实现1.4 层序遍历2. 二叉树的刷题小技巧三. 题目实战1. 力扣 [572. 另一棵树的子树](https://leetcode.cn/problems/subtree-of-another-tree/description/)1.1 题目解析1.2 算法原理1.3 代码2. 力扣 [226. 翻转二叉树](https://leetcode.cn/problems/invert-binary-tree/description/)2.1 题目解析2.2 算法原理2.3 代码3. 力扣 [110. 平衡二叉树](https://leetcode.cn/problems/balanced-binary-tree/description/)3.1 题目解析3.2 算法原理3.3 代码4. 力扣 [101. 对称二叉树](https://leetcode.cn/problems/symmetric-tree/description/)4.1 题目解析4.2 算法原理4.3 代码5. 力扣 [236. 二叉树的最近公共祖先](https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/)5.1 题目解析5.2 算法原理5.3 代码6. 力扣 [105. 从前序与中序遍历序列构造二叉树](https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/)6.1 题目解析6.2 算法原理6.3 代码7. 力扣 [106. 从中序与后序遍历序列构造二叉树](https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/)7.1 题目解析7.2 算法原理7.3 代码8. 力扣 [606. 根据二叉树创建字符串](https://leetcode.cn/problems/construct-string-from-binary-tree/)8.1 题目解析8.2 算法原理8.3 代码一. 介绍1. 树的基本特性树是一种非线性数据结构子树间不相交一个结点也可以被称为树空结点为空树除了根结点root外每个子结点有且只有一个父结点一颗 N 个结点的树有 N-1 条边一个结点含有的所有子树的个数称为该结点的度所有结点中度的最大值就是整颗树的度度为0的结点为叶子结点一个结点含有子结点那么就是其子结点的父结点一颗树中没有父结点的被称为根结点根结点的最大层就是树的高度/深度—2. 应用场景电脑上的目录就是树结构二. 二叉树1. 二叉树的实现我们从二叉树包含的属性、和其前(先)序遍历、中序遍历、后序遍历、层序遍历这几方面入手树在 Java 中并没有实现出具体的容器但其作为底层结构实现出了 TreeMap、TreeSet、PriorityQueue优先级队列、Stack堆等等容器所以这里我们只讨论二叉树的逻辑结构1.1 前(先)序遍历 - 递归实现前序遍历的口诀是根-左-右即先去根的值再去左结点最后去右结点的值publicvoidpreOrder(TreeNoderoot){if(rootnull){return;}System.out.print(root.val );preOrder(root.left);preOrder(root.right);}1.1 前(先)序遍历 - 迭代实现// 前序迭代实现publicvoiditerationPreOrder(TreeNoderoot){if(rootnull){return;}StackTreeNodestacknewStack();stack.push(root);while(!stack.isEmpty()){TreeNodecurstack.pop();System.out.print(cur.val );if(cur.right!null){stack.push(cur.right);}if(cur.left!null){stack.push(cur.left);}}}1.2 中序遍历 - 递归实现publicvoidinOrder(TreeNoderoot){if(rootnull){return;}inOrder(root.left);System.out.print(root.val );inOrder(root.right);}1.2 中序遍历 - 迭代实现// 中序迭代实现publicvoiditerationInOrder(TreeNoderoot){if(rootnull){return;}StackTreeNodestacknewStack();TreeNodecurroot;while(cur!null||!stack.isEmpty()){// 先遍历所有左子树while(cur!null){stack.push(cur);curcur.left;}// 左子树遍历完成后,打印根的值curstack.pop();System.out.print(cur.val );// 接着cur指向右子树curcur.right;}}1.3 后序遍历 - 递归实现publicvoidpostOrder(TreeNoderoot){if(rootnull){return;}postOrder(root.left);postOrder(root.right);System.out.print(root.val );}1.3 后序遍历 - 迭代实现// 后序迭代实现publicvoiditerationPostOrder(TreeNoderoot){if(rootnull){return;}StackTreeNodestacknewStack();TreeNodecurroot;// 对已访问的结点进行标记TreeNodeprevnull;while(cur!null||!stack.isEmpty()){// 先遍历所有左子树while(cur!null){stack.push(cur);curcur.left;}// 只查看栈顶,不取出TreeNodepeekstack.peek();// 当栈顶元素右子树不为null,且没有被标记,就去右子树(开启下一轮的先左后右)if(peek.right!nullpeek.right!prev){curpeek.right;}else{prevstack.pop();System.out.print(prev.val );}}}1.4 层序遍历借助了队列的先进先出特性publicvoidlevelOrder(TreeNoderoot){if(rootnull){return;}QueueTreeNodequeuenewLinkedList();queue.add(root);while(!queue.isEmpty()){TreeNodecurqueue.poll();System.out.print(cur.val );if(cur.left!null){queue.offer(cur.left);}if(cur.right!null){queue.offer(cur.right);}}}2. 二叉树的刷题小技巧完全二叉树是一种特殊的二叉树如果根结点层数为1则非空二叉树第 i 层最多有 2^(i-1) 个结点 (即满的完全的二叉树)如果根结点层数为1则深度为 K 的树的最大结点个数为 (2^i) - 1 (即满的完全的二叉树)任意一颗二叉树设叶子结点个数为 n0度为2的结点个数为 n2则 n0 n2 1有N个节点的完全二叉树深度 K log2N 向上取整有n个节点的完全二叉树按照层序遍历从上到下从左到右对所有结点编号并假设根节点为 0 号则对于序号 i 的节点有① 如 2i1 n那么左子结点序号为 2i1 否则没有左子结点① 如 2i2 n那么右子结点序号为 2i2 否则没有右子结点有n个节点的完全二叉树按照层序遍历从上到下从左到右对所有结点编号并假设根节点为 1 号则对于序号 i 的节点有① 如 2i ≤ n那么左子结点序号为 2i 否则没有左子结点① 如 2i1 ≤ n那么右子结点序号为 2i1 否则没有右子结点三. 题目实战1. 力扣572. 另一棵树的子树1.1 题目解析子树和相同的树这道题有点类似对于子树的判断方法与这道题一致1.2 算法原理1.3 代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */classSolution{publicbooleanisSubtree(TreeNoderoot,TreeNodesubRoot){if(rootnull){returnfalse;}if(root.valsubRoot.valisSame(root,subRoot)){returntrue;}returnisSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);}publicbooleanisSame(TreeNoderoot,TreeNodesubRoot){if(rootnullsubRootnull){returntrue;}if(rootnullsubRoot!null||root!nullsubRootnull||root.val!subRoot.val){returnfalse;}returnisSame(root.left,subRoot.left)isSame(root.right,subRoot.right);}}2. 力扣226. 翻转二叉树2.1 题目解析除了根结点所有的子结点全部要反转2.2 算法原理用了两个递归函数函数头-发现重复子问题根结点的左子树和右子树都要反转函数体-宏观解决单个子问题① 先反转根结点的作用子结点② 再去把左结点的左子树和右节点的右子树去反转递归的出口(起始点)根结点为空时不需要反转直接返回即可2.3 代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */classSolution{publicTreeNodeinvertTree(TreeNoderoot){if(rootnull){returnroot;}TreeNodetmproot.left;root.leftroot.right;root.righttmp;invertTree(root.left);invertTree(root.right);returnroot;}}3. 力扣110. 平衡二叉树3.1 题目解析平衡二叉树的定义左右子树的高度差不超过 1 空树null也是平衡树3.2 算法原理用了两个递归函数函数头-发现重复子问题① 先计算左右子树的高度② 进行高度差的比较超过 1 的就不是平衡树③ 继续比较所有的左右子树高度差函数体-宏观解决单个子问题① 计算传入结点的整颗树的高度② 整颗树的高度是左右子树的最大高度再 1③ 当是空结点时高度为 0递归的出口(起始点)空树也是平衡树直接返回true3.3 代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */classSolution{publicbooleanisBalanced(TreeNoderoot){if(rootnull){returntrue;}if(Math.abs(calHigh(root.left)-calHigh(root.right))1){returnfalse;}returnisBalanced(root.left)isBalanced(root.right);}intcalHigh(TreeNoderoot){if(rootnull){return0;}returnMath.max(calHigh(root.left),calHigh(root.right))1;}}4. 力扣101. 对称二叉树4.1 题目解析根据根结点成轴对称4.2 算法原理函数头-发现重复子问题判断左右子树是否轴对称函数体-宏观解决单个子问题① 根结点必定轴对称我们只需要判断它的左右子树② 左右子树只要有一个为空或者值不相等说明不对称③ 值一样只能说明当前的左右子结点对称仍要去判断它们的左右子树是否轴对称递归的出口(起始点)左右子树都为空时必定是轴对称4.3 代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */classSolution{publicbooleanisSymmetric(TreeNoderoot){returnisSym(root.left,root.right);}booleanisSym(TreeNodel,TreeNoder){if(lnullrnull){returntrue;}if(lnullr!null||l!nullrnull||l.val!r.val){returnfalse;}returnisSym(l.left,r.right)isSym(l.right,r.left);}}5. 力扣236. 二叉树的最近公共祖先5.1 题目解析结点本身可以是自身的祖先这个是个重点5.2 算法原理函数头-发现重复子问题去左右子树找公共祖先函数体-宏观解决单个子问题① root 等于 q/p 的任意一个就是公共祖先② 去左子树找公共祖先③ 去右子树找公共祖先④ 左右都找到公共祖先时返回根结点⑤ 其中任意一个为空说明公共祖先为另一个递归的出口(起始点)root 等于 null 或者等于q/p 的任意一个就是公共祖先5.3 代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val x; } * } */classSolution{publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){if(rootnull||rootp||rootq){returnroot;}// 去左子树找p或者qTreeNodeleftlowestCommonAncestor(root.left,p,q);// 去左子树找p或者qTreeNoderightlowestCommonAncestor(root.right,p,q);// 左右子树都找到了,root是公共祖先if(left!nullright!null){returnroot;}// 一个为空就返回另一个,不然就返回nullreturnleft!null?left:right;}}6. 力扣105. 从前序与中序遍历序列构造二叉树6.1 题目解析只给遍历顺序借助递归来创建树这里要重点掌握①中序遍历的特性对于任意一个父结点左子树一定在左侧下标中范围不论是否为null右子树一定在右侧下标范围②前序遍历的特性根、左子树、右子树意味着左右子树存在时从左向右遍历表那么右侧第一个一定是左子树6.2 算法原理6.3 代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */classSolution{publicTreeNodebuildTree(int[]preorder,int[]inorder){returncreatTree(preorder,inorder,0,inorder.length-1);}inti0;TreeNodecreatTree(int[]pre,int[]in,intb,inte){if(be){returnnull;}intvalpre[i];TreeNodenodenewTreeNode(val);intindexfindIndex(in,val);i;node.leftcreatTree(pre,in,b,index-1);node.rightcreatTree(pre,in,index1,e);returnnode;}intfindIndex(int[]inorder,intval){for(intj0;jinorder.length;j){if(inorder[j]val){returnj;}}return-1;}}7. 力扣106. 从中序与后序遍历序列构造二叉树7.1 题目解析①中序遍历的特性对于任意一个父结点左子树一定在左侧下标中范围不论是否为null右子树一定在右侧下标范围②后序遍历的特性左子树、右子树、根意味着左右子树存在时倒序遍历表那么左侧第一个一定是右子树7.2 算法原理7.3 代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */classSolution{inti0;publicTreeNodebuildTree(int[]inorder,int[]postorder){iinorder.length-1;returncreatTree(inorder,postorder,0,inorder.length-1);}TreeNodecreatTree(int[]in,int[]post,intb,inte){if(be){returnnull;}intvalpost[i];TreeNodenodenewTreeNode(val);intindexfindIndex(in,val);i--;node.rightcreatTree(in,post,index1,e);node.leftcreatTree(in,post,b,index-1);returnnode;}intfindIndex(int[]inorder,intval){for(intj0;jinorder.length;j){if(inorder[j]val){returnj;}}return-1;}}8. 力扣606. 根据二叉树创建字符串8.1 题目解析这里要注意三个条件① 左子树为空且右子树不为空时要保留空括号② 左子树不为空时先遍历左子树同时整颗左子树要被括起来③ 右子树不为空时再遍历右子树同时整颗右子树要被括起来8.2 算法原理8.3 代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */classSolution{StringBuildersnewStringBuilder();publicStringtree2str(TreeNoderoot){str(root);returns.toString();}voidstr(TreeNoderoot){if(rootnull){return;}s.append(root.val);if(root.left!null){s.append(();str(root.left);s.append());}if(root.leftnullroot.right!null){s.append(());}if(root.right!null){s.append(();str(root.right);s.append());}}}