二叉树先序遍历算法java,由浅入深讲二叉树4种遍历算法的由来
题目一
二叉树题——最大二叉树
根据给定的数组来构建最大二叉树
具体题目如下
解法
/** *二叉树节点的定义。*公共类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解决方案{ public TreeNode construtmaximbinarytree(int[]nums){ return方法(nums，0，nums。长度-1)；}公共TreeNode方法(int[] nums，int lo，int hi){ if(lohi){ return null；} int index=-1；int max=整数。最小值；for(int I=lo；I=hiI){ if(maxnums[I]){ max=nums[I]；index=I；} } TreeNode root=new TreeNode(max)；root.left=method(nums，lo，index-1)；root.right=method(nums，index 1，hi)；返回根目录；}}
题目二
二叉树题——构造二叉树
根据给定的数组按照指定遍历条件构造二叉树并返回根节点
具体题目如下
解法
/** *二叉树节点的定义。*公共类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解决方案{ public TreeNode构建树(int[]preorder，int[]inorder){ return方法(preorder，0，preorder.length-1，inorder，0，in order。长度-1)；} public TreeNode method(int[]preorder，int preLeft，int preEnd，int[] inorder，int inLeft，int inEnd){ if(preLeftpreEnd){ return null；} int root val=preorder[pre left]；int index=-1；for(int I=in left；I=in endi){ if(root val==in order[I]){ index=I；} } TreeNode root=new TreeNode(root val)；int left size=index-in left；root.left=method(preorder，preLeft 1，leftSize preLef
t,inorder,inLeft,index-1); root.right = method(preorder,leftSize+preLeft+1,preEnd,inorder,index+1,inEnd); 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 buildTree(int[] inorder, int[] postorder) { return build(inorder,0,inorder.length-1,postorder,0,postorder.length-1); } TreeNode build(int[] inorder, int inStart, int inEnd,int[] postorder, int postStart, int postEnd) { if (inStart > inEnd) { return null; } // root 节点对应的值就是后序遍历数组的最后一个元素 int rootVal = postorder[postEnd]; // rootVal 在中序遍历数组中的索引 int index = 0; for (int i = inStart; i <= inEnd; i++) { if (inorder[i] == rootVal) { index = i; break; } } // 左子树的节点个数 int leftSize = index - inStart; TreeNode root = new TreeNode(rootVal); // 递归构造左右子树 root.left = build(inorder, inStart, index - 1,postorder, postStart, postStart + leftSize - 1); root.right = build(inorder, index + 1, inEnd,postorder, postStart + leftSize, postEnd - 1); 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 constructFromPrePost(int[] preorder, int[] postorder) { return method(preorder,0,preorder.length-1,postorder,0,postorder.length-1); } public TreeNode method(int[] preorder,int preStart, int preEnd, int[] postorder,int postStart,int postEnd){ if(preStart>preEnd){ return null; } if(preStart==preEnd){ return new TreeNode(preorder[preStart]); } int rootVal = preorder[preStart]; int leftRootVal = preorder[preStart + 1]; int index = 0; for (int i = postStart; i < postEnd; i++) { if (postorder[i] == leftRootVal) { index = i; break; } } TreeNode root = new TreeNode(rootVal); int leftSize = index - postStart + 1; root.left = method(preorder, preStart + 1, preStart + leftSize,postorder, postStart, index); root.right = method(preorder, preStart + leftSize + 1, preEnd,postorder, index + 1, postEnd - 1); return root; }}到此这篇关于剑指Offer之Java算法习题精讲二叉树的构造和遍历的文章就介绍到这了,更多相关Java 二叉树构造内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。