做外贸 是否需要做中文网站,网站建设维护的知识,房产公司网站建设方案,wordpress 主题 设计1. 前序和中序遍历 **思路#xff1a;我们每一次一定可以根据递归确定根节点是哪个#xff0c;就是前序第一个数#xff0c;然后找中序遍历这个点#xff0c;看左子树有几个节点#xff0c;右子树有几个节点#xff0c;然后就可以根据节点个数#xff0c;递归左子树和右…1. 前序和中序遍历 **思路我们每一次一定可以根据递归确定根节点是哪个就是前序第一个数然后找中序遍历这个点看左子树有几个节点右子树有几个节点然后就可以根据节点个数递归左子树和右子树当且仅当leftright时结束由于preorder和inorder对应的所以leftright只需要判断一个符不符合就行了。**8个位置的判断一定要仔细。借助hashmap确定中序遍历某个节点的位置。
class Solution {MapInteger,Integer mp new HashMap();int n;TreeNode PreMidTreeBuilder(int[] preorder,int[] inorder,int preorder_left, int preorder_right, int inorder_left, int inorder_right){if(preorder_leftpreorder_right) return null;TreeNode root new TreeNode(0,null,null);int rootNodeVal preorder[preorder_left];root.val rootNodeVal;//定位到中序遍历的位置int inorderRoot mp.get(rootNodeVal);//可以根据坐标定下来左右子树的节点数量int leftLength inorderRoot-inorder_left;int rightLength inorder_right-inorderRoot;root.leftPreMidTreeBuilder(preorder,inorder,preorder_left1,preorder_leftleftLength,inorder_left,inorderRoot-1); root.rightPreMidTreeBuilder(preorder,inorder,preorder_leftleftLength1,preorder_right,inorderRoot1,inorder_right);return root;}public TreeNode buildTree(int[] preorder, int[] inorder) {n preorder.length;for(int i0;in;i)mp.put(inorder[i],i);return PreMidTreeBuilder(preorder,inorder,0,n-1,0,n-1);}
}2. 中序和后序遍历
和前序中序完全一样的思路可以说所有这种题都是这个思路。
class Solution { MapInteger,Integer map new HashMap();public TreeNode buildInPostTree(int[] inorder, int[] postorder,int inorder_left,int inorder_right,int postorder_left,int postorder_right){if(inorder_leftinorder_right)return null;int val postorder[postorder_right];int inorder_root map.get(val);int nums_left_tree inorder_root-inorder_left;int nums_right_tree inorder_right-inorder_root;TreeNode root new TreeNode(val,null,null);root.left buildInPostTree(inorder,postorder,inorder_left,inorder_leftnums_left_tree-1,postorder_left,postorder_leftnums_left_tree-1);root.right buildInPostTree(inorder,postorder,inorder_root1,inorder_right,postorder_right-nums_right_tree,postorder_right-1);return root; }public TreeNode buildTree(int[] inorder, int[] postorder) {int n inorder.length;for(int i0;in;i)map.put(inorder[i],i);return buildInPostTree(inorder,postorder,0,n-1,0,n-1);}
}
