劍指Offer之Java算法習(xí)題精講二叉樹的構(gòu)造和遍歷
題目一
二叉樹題——最大二叉樹
根據(jù)給定的數(shù)組來構(gòu)建最大二叉樹
具體題目如下
解法
/** * 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 constructMaximumBinaryTree(int[] nums) { return method(nums,0,nums.length-1); } public TreeNode method(int[] nums,int lo,int hi){ if(lo>hi){ return null; } int index = -1; int max = Integer.MIN_VALUE; for(int i = lo;i<=hi;i++){ if(max<nums[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); return root; } }
題目二
二叉樹題——構(gòu)造二叉樹
根據(jù)給定的數(shù)組按照指定遍歷條件構(gòu)造二叉樹并返回根節(jié)點
具體題目如下
解法
/** * 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[] preorder, int[] inorder) { return method(preorder,0,preorder.length-1,inorder,0,inorder.length-1); } public TreeNode method(int[] preorder, int preLeft,int preEnd , int[] inorder,int inLeft,int inEnd){ if(preLeft>preEnd){ return null; } int rootVal = preorder[preLeft]; int index = -1; for(int i = inLeft;i<=inEnd;i++){ if(rootVal == inorder[i]){ index = i; } } TreeNode root = new TreeNode(rootVal); int leftSize = index - inLeft; root.left = method(preorder,preLeft+1,leftSize+preLeft,inorder,inLeft,index-1); root.right = method(preorder,leftSize+preLeft+1,preEnd,inorder,index+1,inEnd); return root; } }
題目三
二叉樹題——構(gòu)造二叉樹
根據(jù)給定的數(shù)組按照指定遍歷條件構(gòu)造二叉樹并返回根節(jié)點
具體題目如下
解法
/** * 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 節(jié)點對應(yīng)的值就是后序遍歷數(shù)組的最后一個元素 int rootVal = postorder[postEnd]; // rootVal 在中序遍歷數(shù)組中的索引 int index = 0; for (int i = inStart; i <= inEnd; i++) { if (inorder[i] == rootVal) { index = i; break; } } // 左子樹的節(jié)點個數(shù) int leftSize = index - inStart; TreeNode root = new TreeNode(rootVal); // 遞歸構(gòu)造左右子樹 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; } }
題目四
二叉樹題——構(gòu)造二叉樹
根據(jù)給定的數(shù)組按照指定遍歷條件構(gòu)造二叉樹并返回
具體題目如下
解法
/** * 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; } }
到此這篇關(guān)于劍指Offer之Java算法習(xí)題精講二叉樹的構(gòu)造和遍歷的文章就介紹到這了,更多相關(guān)Java 二叉樹構(gòu)造內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- 劍指Offer之Java算法習(xí)題精講鏈表與數(shù)組專項訓(xùn)練
- 劍指Offer之Java算法習(xí)題精講鏈表與二叉樹專項訓(xùn)練
- 劍指Offer之Java算法習(xí)題精講二叉樹專項訓(xùn)練
- 劍指Offer之Java算法習(xí)題精講數(shù)組與二叉樹
- 劍指Offer之Java算法習(xí)題精講鏈表與字符串及數(shù)組
- 劍指Offer之Java算法習(xí)題精講二叉搜索樹與數(shù)組查找
- 劍指Offer之Java算法習(xí)題精講數(shù)組與字符串題
- 劍指Offer之Java算法習(xí)題精講字符串與二叉搜索樹
- 劍指Offer之Java算法習(xí)題精講數(shù)組查找與字符串交集
相關(guān)文章
Eclipse安裝Aptana插件(注意對應(yīng)版本問題)
這篇文章主要為大家詳細介紹了Eclipse安裝Aptana插件的相關(guān)資料,特別注意對應(yīng)版本問題,具有一定的參考價值,感興趣的小伙伴們可以參考一下2017-02-02java Class.getSimpleName() 詳解及用法
這篇文章主要介紹了java Class.getSimpleName() 詳解及用法的相關(guān)資料,需要的朋友可以參考下2017-02-02