编写一些高效率的函数,只使用指向二叉树,设计一个算法求出指定节点在二叉树中的层次
题目一
二叉树题——查找二叉树
根据给定的二叉树根节点和指定条件查找其中指定元素
具体题目如下
解法
/** *二叉树节点的定义。*公共类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 * } * } */class解{ int I=0；int RES=0；public int k th small(TreeNode root，int k) { method(root，k)；返回res}公共无效方法(TreeNode root，int k){ if(root==null)return；方法(root.left，k)；我；if(I==k){ RES=root。val返回；}方法(root.right，k)；}}
题目二
二叉树题——转换累加树
根据给定的二叉树根节点按指定条件转换为累加树
具体题目如下
解法
/** *二叉树节点的定义。*公共类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 * } * } */class求解{ int sum=0；public TreeNode convert BST(TreeNode root){ method(root)；返回根目录；}公共空间方法(TreeNode root){ if(root==null){ return；}方法(根。对)；sum=root.valroot.val=sum方法(根。左)；}}
题目三
二叉树题——验证二叉树
根据给定的二叉树根节点判断它是不是有效的二叉搜索树
具体题目如下
解法
/** *二叉树节点的定义。*公共类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 * } * } */class Solution { public boolean是有效的BST(TreeNode
root) { return method(root,null,null); } public boolean method(TreeNode root,TreeNode min,TreeNode max){ if(root==null) return true; if(min!=null&&root.val<=min.val) return false; if(max!=null&&root.val>=max.val) return false; return method(root.left,min,root)&&method(root.right,root,max); }}
题目四
二叉树题——搜索二叉树
根据给定的二叉树根节点查找其中指定的数值
具体题目如下
解法
/** * 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; * } * } */class Solution { public TreeNode searchBST(TreeNode root, int val) { if(root==null) return null; if(root.val==val) return root; if(root.val>=val){ return searchBST(root.left,val); } if(root.val<val){ return searchBST(root.right,val); } return null; }}题目五
二叉树题——二叉树操作
根据给定的二叉树根节点将指定的数值插入二叉树
具体题目如下
解法
/** * 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; * } * } */class Solution { public TreeNode insertIntoBST(TreeNode root, int val) { return method(root,val); } public TreeNode method(TreeNode root, int val){ if(root==null) return new TreeNode(val); if (root.val < val) root.right = insertIntoBST(root.right, val); if (root.val > val) root.left = insertIntoBST(root.left, val); return root; }}题目六
二叉树题——二叉树操作
根据给定的二叉树根节点在不改变二叉树性质的条件下删除其中指定的数值对应的节点
具体题目如下
算法
/** * 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; * } * } */class Solution { public TreeNode deleteNode(TreeNode root, int key) { if (root == null) return null; if (root.val == key){ if (root.left == null) return root.right; if (root.right == null) return root.left; TreeNode minNode = getMin(root.right); root.right = deleteNode(root.right, minNode.val); minNode.left = root.left; minNode.right = root.right; root = minNode; }else if(root.val>key){ root.left = deleteNode(root.left,key); }else{ root.right = deleteNode(root.right,key); } return root; } TreeNode getMin(TreeNode node) { while (node.left != null) node = node.left; return node; } }到此这篇关于剑指Offer之Java算法习题精讲二叉树专项训练的文章就介绍到这了,更多相关Java 二叉树内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。