132 先序遍历构造二叉树

问题描述：返回与给定先序遍历相匹配的二叉搜索输的根节点。

求解思路：对于先序遍历而言，第一个遍历的元素是根节点，然后遍历左子树，则可以在找到第一个根节点之后继续往右走，找到第一个大于根节点(第一个元素的)的元素即为右子树节点，不停地依据该方法进行递归调用即可。

Public TreeNode rebuildTree(int []preorders,int begin,int end)
{
if(begin>end){return null;}
TreeNode newNode=new TreeNode();
newNode.val=preorders[begin];
int index=begin;
for(int i=begin+1;i<=end;i++)
{
if(preorders[i]>preorders[begin]){index=i;break;}
}
newNode.left=rebuildTree(preorders,begin+1,index-1);
newNode.right=rebuildTree(preorders,index,end);
}
public treeNode RebuildTree(int []preorders)
{
return rebuildTree(preorders,0,preorders.length-1);
}

采用先序遍历的方法来解决，首先定义一个全局的index表示当前访问到哪个节点了，而且在访问了当前根节点(index指向的那个节点时)，在后续访问左节点和右节点的时候将当前值传入函数中，对子节点不能大于该值，右子节点不能小于该值，不然退出当前函数dfs，进入下一个dfs函数中。

int index=0;
public TreeNode preLeft(int[]preorders,int max)
{
if(index>=preorders.length){return null;}
if(preorders[index]>max){return null;}
else
{
TreeNode newNode=new TreeNode();
newNode.val=preorders[index];
index++;
newNode.left=preLeft(preorders,newNode.val);
newNode.right=preRight(preorders,newNode.val);
}
}
?

public TreeNode preRight(int[]preorders,int min)
{
if(index>=preorders.length){return null;}
if(preorders[index]<min){return null;}
else
{
TreeNode newNode=new TreeNode();
newNode.val=preorders[index];
index++;
newNode.left=preLeft(preorders,newNode.val);
newNode.right=preRight(preorders,newNode.val);
}
}
public TreeNode preRebuild(int[]preorders)
{
TreeNode root=new TreeNode();
root.val=preorders[index];
index++;
root.left=preLeft(preorders,root.val);
root.right=preRight(preorders,root.val);
???????return root;
}

stack栈求解：定义一个TreeNode节点的栈，首先把根节点放入其中，接着遍历preorder这个数组，如果stack上的第一个元素大于当前便利的preorder这个元素，则表示这个元素是stack这个顶部元素的左子结点，更新后，将该节点放入stack中，如果比stack的顶部元素大，则一直出栈，直到stack的顶部元素比preorder当前元素大，则将弹出的前一个元素的右节点定义为该元素。

public TreeNode stackSolution(int[]preorders)
{
Stack<TreeNode>stack=new Stack<>();
TreeNode root=new TreeNode<>();
root.val=preorders[0];
for(int i=1;i<preorders.length;i++)
{
if(stack.peek().val>preorders[i])
{
TreeNode left=new TreeNode<>();
left.val=preorders[i];
stack.peek().left=left;
stack.push(left);
}else
{
TreeNode pre=stack.pop();
while(stack.peek().val<preorders[i])
{
pre=stack.pop();
}
TreeNode right=new TreeNode<>();
right.val=preorders[i];
pre.right=right;
stack.push(right);
}
}
???????return root;
}