剑指Offer之Java算法习题精讲二叉树的构造和遍历

剑指Offer之Java算法习题精讲二叉树的构造和遍历

题目一

解法

/**

* 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

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;

}

}

题目二

解法

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode() {}

* TreeNode(ihttp://nt 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;

}

}

题目三

解法

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode() zYNcow{}

* 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.vazYNcowl = 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;

}

}

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;

}

}

题目二

解法

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode() {}

* TreeNode(ihttp://nt 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;

}

}

题目三

解法

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode() zYNcow{}

* 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.vazYNcowl = 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;

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。