四道题弄懂根据遍历顺序构造二叉树

本文主要是介绍四道题弄懂根据遍历顺序构造二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

模板：

构造二叉树:

public TreeNode f(..){TreeNode root=..;root.left=f(..);root.right=f(..);return root;
}

 根据序列构造二叉树：

Map<Integet,Integet>
public main(int[] nums){return f(nums,0,nums.length-1);
}
public TreeNode f(int[] nums,int left,int right){if(left>right)    return null;TreeNode root=new TreeNode(nums[index]);int k=map.get(index);root.left=f(nums,left,k-1);root.right=f(nums,k+1,right);return root;
} 

1.合并二叉树（LeetCode617）

class Solution {public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {if (t1 == null) {return t2;}if (t2 == null) {return t1;}TreeNode merged = new TreeNode(t1.val + t2.val);merged.left = mergeTrees(t1.left, t2.left);merged.right = mergeTrees(t1.right, t2.right);return merged;}
}

2.最大二叉树（LeetCode654）

模板题

class Solution {Map<Integer,Integer> map=new HashMap<>();public TreeNode constructMaximumBinaryTree(int[] nums) {for(int i=0;i<nums.length;i++)  map.put(nums[i],i);return f(nums,0,nums.length-1);}public TreeNode f(int[] nums,int left,int right){if(left>right)  return null;int max=-1;for(int i=left;i<=right;i++)    max=Math.max(max,nums[i]);int k=map.get(max);TreeNode root=new TreeNode(max);root.left=f(nums,left,k-1);root.right=f(nums,k+1,right);return root;}
}

3.从前序与中序遍历构造二叉树（LeetCode105）

class Solution {Map<Integer,Integer> map=new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {for(int i=0;i<inorder.length;i++)   map.put(inorder[i],i);return f(preorder,inorder,0,preorder.length-1,0,inorder.length-1);}public TreeNode f(int[] preorder,int[] inorder,int pLeft,int pRight,int inLeft,int inRight){if(pLeft>pRight)    return null;TreeNode root=new TreeNode(preorder[pLeft]);int k=map.get(root.val);root.left=f(preorder,inorder,pLeft+1,pLeft+1+k-1-inLeft,inLeft,k-1);root.right=f(preorder,inorder,pLeft+1+k-1-inLeft+1,pRight,k+1,inRight);return root;}
}

4.从中序和后序遍历构造二叉树（LeetCode106）

class Solution {Map<Integer,Integer> map=new HashMap<>();public TreeNode buildTree(int[] inorder, int[] postorder) {for(int i=0;i<inorder.length;i++)   map.put(inorder[i],i);return f(postorder,inorder,0,postorder.length-1,0,inorder.length-1);}public TreeNode f(int[] postorder,int[] inorder,int pLeft,int pRight,int inLeft,int inRight){if(pLeft>pRight)    return null;TreeNode root=new TreeNode(postorder[pRight]);int k=map.get(root.val);root.left=f(postorder,inorder,pLeft,pRight-1-inRight+k,inLeft,k-1);root.right=f(postorder,inorder,pRight-1-inRight+k+1,pRight-1,k+1,inRight);return root;}
}

这篇关于四道题弄懂根据遍历顺序构造二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---