Java教程
二叉树算法
本文主要是介绍二叉树算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
文章目录
- 重建二叉树
- 验证二叉搜索树
- 平衡二叉树
- 判断是否为完全二叉树
- 二叉树最大深度
- 二叉树最小深度
- 求⼆叉树中节点的个数
- 求⼆叉树中叶⼦节点的个数
- 求⼆叉树中第k层节点的个数
- 判断⼆叉树是否是平衡⼆叉树
- 判断一棵二叉树是否为搜索二叉树和完全二叉树
- 两个⼆叉树是否完全相同
- 两个⼆叉树是否互为镜像
- 翻转⼆叉树or镜像⼆叉树
- 在二叉树中找到两个节点的最近公共祖先
- 二叉树遍历
- 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树
- 给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
- 二叉树根节点到叶子节点和为指定值的路径
- 二叉树右视图
- 二叉树的之字形层序遍历
- 判断二叉树是否对称
- 操作给定的二叉树，将其变换为源二叉树的镜像。
- 最大路径和
- 将有序数组转换为二叉搜索树
- 二叉树中是否存在节点和为指定值的路径
- 合并二叉树
重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
Java HashMap 操作：
//添加元素 put()
//访问元素 get(key)
//删除元素 remove(key)
//清空所有键值对 clear()
//计算大小 size()
//判断是否为空 isEmpty()
//检查 hashMap 中是否存在指定的 key 对应的映射关系。containsKey()
//检查 hashMap 中是否存在指定的 value 对应的映射关系 containsValue()
//替换 hashMap 中是指定的 key 对应的 value。如果 hashMap 中是否存在指定的 value 对应的映射关系返回 true，否则返回 false。
//replace(K key, V oldValue, V newValue)
//遍历
HashMap<Integer, String> Sites = new HashMap<Integer, String>();
// 添加键值对
Sites.put(1, "Google");
Sites.put(2, "Runoob");
// 输出 key 和 value
for (Integer i : Sites.keySet()) {
System.out.println("key: " + i + " value: " + Sites.get(i));
}
// 返回所有 value 值
for(String value: Sites.values()) {
// 输出每一个value
System.out.print(value + ", ");
}
}
//方法一 递归
//哈希表的初始化
class Solution {
private Map<Integer, Integer> indexMap;
public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
if (preorder_left > preorder_right) {
return null;
}
// 前序遍历中的第一个节点就是根节点
int preorder_root = preorder_left;
// 在中序遍历中定位根节点
int inorder_root = indexMap.get(preorder[preorder_root]);
// 先把根节点建立出来
TreeNode root = new TreeNode(preorder[preorder_root]);
// 得到左子树中的节点数目
int size_left_subtree = inorder_root - inorder_left;
// 递归地构造左子树，并连接到根节点
// 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
// 递归地构造右子树，并连接到根节点
// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
int n = preorder.length;
// 构造哈希映射，帮助我们快速定位根节点
indexMap = new HashMap<Integer, Integer>();
for (int i = 0; i < n; i++) {
indexMap.put(inorder[i], i);
}
return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
}
}
验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
方法一：
如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。
class Solution {
public boolean isValidBST(TreeNode root) {
if(root == null) return true;
return func(root, Long.MIN_VALUE,Long.MAX_VALUE);
}
private boolean func(TreeNode root,long l,long r){
if(root == null) return true;
if(root.val <=l||root.val >=r) return false;
return func(root.left,l,root.val) && func(root.right,root.val,r);
}
}
方法二：
二叉搜索树「中序遍历」得到的值构成的序列一定是升序的，这启示我们在中序遍历的时候实时检查当前节点的值是否大于前一个中序遍历到的节点的值即可。如果均大于说明这个序列是升序的，整棵树是二叉搜索树，否则不是
public boolean isValidBST(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
double pre = -Double.MAX_VALUE;
while(!stack.isEmpty() || root !=null){
while(root !=null){
stack.push(root);
root = root.left;
}
root = stack.pop();
if(root.val <=pre ) return false;
pre = root.val;
root = root.right;
}
return true;
}
平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
return Math.abs(func(root.left)-func(root.right))<=1 && isBalanced(root.left) && isBalanced(root.right);
}
private int func(TreeNode root){
if(root == null) return 0;
return Math.max(func(root.left)+1,func(root.right)+1);
}
判断是否为完全二叉树
题目判断一个棵二叉树是否为完全二叉树
判断一个棵二叉树是否为完全二叉树，完全二叉树的特点就是，除了叶子节点，其余节点都是满枝的，并且叶子节点都是尽最大可能的向左聚集的（即叶子节点的空节点都在最后面）。
// 验证是否为完全二叉树
public boolean isFull(TreeNode root){
Queue<TreeNode> queue= new LinkedList<TreeNode>();
if(root != null){
queue.add(root);
}
while(!queue.isEmpty()){
TreeNode node = queue.poll();
if(node != null){
queue.add(node.left);
queue.add(node.right);
}else{
// 如果节点为nul,则去判断后面的节点中是否还存在不为null，
// 如果还存在不为null的节点，则不是完全二叉树
// 因为完全二叉树，要么叶子节点都是满的，要么都聚集在左节点上，所以聚集在左节点上，所有的null都在最后面。
while(!queue.isEmpty()){
TreeNode leafNode = queue.poll();
if(leafNode != null){
return false;
}
}
}
}
return true;
}
https://www.cnblogs.com/andy-songwei/p/13898705.html
https://www.cnblogs.com/wangfeihu/p/5977558.html
二叉树最大深度
思路：递归思想，分别递归求解左右子树深度，总深度=左右子树中较深的那个深度+1
public int TreeDepth(TreeNode root) {
if(root == null){
return 0;
}
int left = TreeDepth(root.left);
int right = TreeDepth(root.right);
return 1+(left>right?left:right);
}
二叉树最小深度
思路
还是递归，最小深度与最大深度的不同是：
如果是那种只有一个方向的子树，即"根节点–>左子树–>左子树–>左子树–>左子树" ，或“根节点–>右子树–>右子树–>右子树–>右子树”（这种情况对应的条件是，左子树或者右子树的最小高度为0，也就是木有左子树或者右子树），
则最后结果是：1+left+right，也就是所有子树高度之和。
除了上述特殊情况外，其余正常的有左右子树的，就递归第求出左右子树中较小的那个深度：1+(Math.min(left,right))，即为整棵树的最小深度。
public int minDepth(TreeNode root) {
if(root == null) return 0;
int left = minDepth(root.left);
int right = minDepth(root.right);
return left!=0 && right!=0 ? 1+(Math.min(left,right)):1+left+right;
}
求⼆叉树中节点的个数
思路：
当树为空时，结点个数为0，否则为根节点个数 加上 根的左子树中节点个数 再加上 根的右子树中节点的个数
借助遍历二叉树的思路，每访问一个结点，计数增1
求⼆叉树中叶⼦节点的个数
思路：
1)当树为空时，叶子结点个数为0
2)当某个节点的左右子树均为空时，表明该结点为叶子结点，返回1
3)当某个节点有左子树，或者有右子树时，或者既有左子树又有右子树时，说明该节点不是叶子结点，因此叶结点个数等于左子树中叶子结点个数 加上 右子树中叶子结点的个数
求⼆叉树中第k层节点的个数
判断⼆叉树是否是平衡⼆叉树
一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
private int depth(TreeNode root) {
if (root == null) return 0;
return Math.max(depth(root.left), depth(root.right)) + 1;
}
}
判断一棵二叉树是否为搜索二叉树和完全二叉树
思路：判断一棵二叉树是否为二叉搜索树，二叉搜索树的特点是，左子树都小于根节点，右子树都大于根节点。所以我们可以通过递归来实现，先判断root节点是否满足，再去判断左子树上的节点和右子树上的节点是否满足。
判断一个棵二叉树是否为完全二叉树，完全二叉树的特点就是，除了叶子节点，其余节点都是满枝的，并且叶子节点都是尽最大可能的向左聚集的（即叶子节点的空节点都在最后面）。
public boolean[] judgeIt (TreeNode root) {
// write code here
// write code here
if(root == null){
return new boolean[]{true,true};
}
boolean bst = isBST(root,null,null);
boolean full = isFull(root);
return new boolean[]{bst,full};
}
public boolean isBST(TreeNode root,Integer low,Integer hight){
if(root == null){
return true;
}
// 如果root值小于最低项则不是搜索二叉树
if(low != null && root.val <= low){
return false;
}
// 如果root值大于最高项，也不是二叉搜索树
if(hight != null && root.val >= hight){
return false;
}
boolean left = isBST(root.left,low,root.val);
boolean right = isBST(root.right,root.val,hight);
return left && right;
}
// 验证是否为完全二叉树
public boolean isFull(TreeNode root){
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
TreeNode temp = queue.poll();
if(temp !=null){
queue.add(temp.left);
queue.add(temp.right);
}else{
while(!queue.isEmpty()){
if(queue.poll() != null) return false;
}
}
}
return true;
}
两个⼆叉树是否完全相同
两个⼆叉树是否互为镜像
翻转⼆叉树or镜像⼆叉树
TreeNode mirrorTreeNode(TreeNode root){
if(root == null) return null;
TreeNode left = mirrorTreeNode(root.left);
TreeNode right = mirrorTreeNode(root.right);
root.left = right;
root.right = left;
return root;
}
在二叉树中找到两个节点的最近公共祖先
思路：
我们可以用哈希表存储所有节点的父节点，然后我们就可以利用节点的父节点信息从 p 结点开始不断往上跳，并记录已经访问过的节点，再从 q 节点开始不断往上跳，如果碰到已经访问过的节点，那么这个节点就是我们要找的最近公共祖先。
class Solution {
Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
Set<Integer> visited = new HashSet<Integer>();
public void dfs(TreeNode root) {
if (root.left != null) {
parent.put(root.left.val, root);
dfs(root.left);
}
if (root.right != null) {
parent.put(root.right.val, root);
dfs(root.right);
}
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dfs(root);
while (p != null) {
visited.add(p.val);
p = parent.get(p.val);
}
while (q != null) {
if (visited.contains(q.val)) {
return q;
}
q = parent.get(q.val);
}
return null;
}
}
二叉树遍历
前序遍历
//递归
public static void preOrderRecur(TreeNode head) {
if (head == null) {
return;
}
System.out.print(head.value + " ");
preOrderRecur(head.left);
preOrderRecur(head.right);
}
//迭代
public static void preOrderIteration(TreeNode head) {
if (head == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(head);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.print(node.value + " ");
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
中序遍历
public static void preOrderRecur(TreeNode head) {
if (head == null) {
return;
}
preOrderRecur(head.left);
System.out.print(head.value + " ");
preOrderRecur(head.right);
}
//迭代
public static void inOrderIteration(TreeNode head) {
if (head == null) {
return;
}
TreeNode cur = head;
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || cur != null) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.pop();
System.out.print(node.value + " ");
if (node.right != null) {
cur = node.right;
}
}
}
后序遍历
public static void postOrderRecur(TreeNode head) {
if (head == null) {
return;
}
postOrderRecur(head.left);
postOrderRecur(head.right);
System.out.print(head.value + " ");
}
public static void postOrderIteration(TreeNode head) {
if (head == null) {
return;
}
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
stack1.push(head);
while (!stack1.isEmpty()) {
TreeNode node = stack1.pop();
stack2.push(node);
if (node.left != null) {
stack1.push(node.left);
}
if (node.right != null) {
stack1.push(node.right);
}
}
while (!stack2.isEmpty()) {
System.out.print(stack2.pop().value + " ");
}
}
层次遍历
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
// write code here
TreeNode q = root;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(q);
ArrayList<ArrayList<Integer>> all = new ArrayList<>();
if(root == null) return all;
while(!queue.isEmpty()){
ArrayList<Integer> list = new ArrayList<>();
int size = queue.size();
for(int i=0;i<size;++i){
TreeNode temp = queue.poll();
list.add(temp.val);
if(temp.left !=null) queue.add(temp.left);
if(temp.right !=null) queue.add(temp.right);
}
all.add(list);
}
return all;
}
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树
private Map<Integer,Integer> map;
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
map = new HashMap<>();
for(int i=0;i<in.length;++i){
map.put(in[i],i);
}
return f(pre,in,0,pre.length-1,0,in.length-1);
}
private TreeNode f(int[] pre,int []in,int pstart,int pend,int istart,int iend){
if(pstart>pend) return null;
TreeNode root = new TreeNode(pre[pstart]);
int leftsize = map.get(pre[pstart])-istart;
root.left = f(pre,in,pstart+1,pstart+leftsize,istart,map.get(pre[pstart])-1);
root.right = f(pre,in,pstart+leftsize+1,pend,map.get(pre[pstart])+1,iend);
return root;
}
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
class Solution {
int pre;
int ans;
public int minDiffInBST(TreeNode root) {
ans = Integer.MAX_VALUE;
pre = -1;
dfs(root);
return ans;
}
public void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
if (pre == -1) {
pre = root.val;
} else {
ans = Math.min(ans, root.val - pre);
pre = root.val;
}
dfs(root.right);
}
}
二叉树根节点到叶子节点和为指定值的路径
ArrayList<ArrayList<Integer>> res;
public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
// write code here
res = new ArrayList<>();
if(root == null) return res;
ArrayList<Integer> path = new ArrayList<>();
path.add(root.val);
dfs(root,sum,path);
return res;
}
private void dfs(TreeNode root,int sum, ArrayList<Integer> path){
if(root.left == null && root.right == null && ad(path) == sum){
res.add(new ArrayList<>(path));
}else{
if(root.left != null){
path.add(root.left.val);
dfs(root.left,sum,path);
path.remove(path.size()-1);
}
if(root.right !=null){
path.add(root.right.val);
dfs(root.right,sum,path);
path.remove(path.size()-1);
}
}
}
private int ad(ArrayList<Integer> path){
int res = 0;
for(Integer i:path) res+=i;
return res;
}
二叉树右视图
思路
层次遍历 输出每一层最后一个。
public List<Integer> rightSideView(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) return list;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
int size = queue.size();
for(int i=0;i<size;++i){
TreeNode temp = queue.poll();
if(temp.left != null) queue.add(temp.left);
if(temp.right != null) queue.add(temp.right);
if(i == size -1) list.add(temp.val);
}
}
return list;
}
二叉树的之字形层序遍历
re.add(0,temp.val); 头插法
public ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) {
// write code here
ArrayList<ArrayList<Integer>> arr = new ArrayList<>();
Queue<TreeNode> qu = new LinkedList<>();
qu.add(root);
int le = 1;
if(root !=null)
while(!qu.isEmpty()){
int size = qu.size();
ArrayList<Integer> re = new ArrayList<>();
for(int i=0;i<size;++i){
TreeNode temp = qu.poll();
if(le%2==0) re.add(0,temp.val);
else re.add(temp.val);
if(temp.left!=null) qu.add(temp.left);
if(temp.right!=null) qu.add(temp.right);
}
arr.add(new ArrayList<>(re));
le++;
}
return arr;
}
判断二叉树是否对称
public boolean isSymmetric (TreeNode root) {
// write code here
if(root == null) return true;
Queue<TreeNode> qu = new LinkedList<>();
qu.offer(root.left);
qu.offer(root.right);
while(!qu.isEmpty()){
TreeNode left = qu.poll();
TreeNode right = qu.poll();
if(left == null && right == null) continue;
if(left==null || right ==null) return false;
if(left.val != right.val) return false;
qu.offer(left.left);
qu.offer(right.right);
qu.offer(left.right);
qu.offer(right.left);
}
return true;
}
操作给定的二叉树，将其变换为源二叉树的镜像。
public TreeNode Mirror (TreeNode pRoot) {
// write code here
if(pRoot == null) return null;
Mirror(pRoot.left);
TreeNode left = pRoot.left;
pRoot.left = pRoot.right;
pRoot.right = left;
Mirror(pRoot.left);
return pRoot;
}
最大路径和
参考
将有序数组转换为二叉搜索树
思路：使用递归的方式，每次取数组中间的值比如m作为当前节点，m前面的值都是比 他小的，作为他左子树的结点值。m后面的值都是比他大的，作为他右子树的节点值
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if(nums.length == 0) return null;
return dfs(nums,0,nums.length -1);
}
private TreeNode dfs(int nums[],int start,int end){
if(start > end) return null;
int mid = (start+end) >>1;
TreeNode root = new TreeNode(nums[mid]);
root.left = dfs(nums,start,mid-1);
root.right = dfs(nums,mid+1,end);
return root;
}
}
二叉树中是否存在节点和为指定值的路径
boolean flag = false;
public boolean hasPathSum (TreeNode root, int sum) {
// write code here
if(root == null) return false;
func(root,0,sum);
return flag;
}
private void func(TreeNode root,int cur,int sum){
if(root == null ) return ;
cur+=root.val;
if(root.left ==null && root.right==null){
if(sum == cur) flag = true;
}else{
func(root.left,cur,sum);
func(root.right,cur,sum);
}
}
合并二叉树
已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替
public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
if(t1 == null) return t2;
if(t2 == null) return t1;
t1.val += t2.val;
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
}
这篇关于二叉树算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
Springboot应用的多环境打包入门11-23
-
Springboot应用的生产发布入门教程11-23
-
Python编程入门指南11-23
-
Java创业入门：从零开始的编程之旅11-23
-
Java创业入门：新手必读的Java编程与创业指南11-23
-
Java对接阿里云智能语音服务入门详解11-23
-
Java对接阿里云智能语音服务入门教程11-23
-
JAVA对接阿里云智能语音服务入门教程11-23
-
Java副业入门：初学者的简单教程11-23
-
JAVA副业入门：初学者的实战指南11-23
-
JAVA项目部署入门：新手必读指南11-23
-
Java项目部署入门：新手必看指南11-23
-
Java项目部署入门：新手必读指南11-23
-
Java项目开发入门：新手必读指南11-23
-
JAVA项目开发入门：从零开始的实用教程11-23
栏目导航
