二叉树的后序遍历(Java)

谁借莪１个温暖的怀抱￠ 2022-05-14 12:48 118阅读 0赞

**题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。**

**二叉搜索树：左子树的所有结点小于根结点 && 右子树的所有结点大于根节点；**

**二叉搜搜索树的后序遍历：遍历的最后一个元素是树的根节点；**

**基于以上两点，遍历的数组可以分为两部分，前半部分是左子树的值，后半部分是右子树的值，需要用递归的方法（即：左子树部分的数组最后一个元素是左子树的根节点）对树的左子树和右子树部分进行同样的操作；**

**实例：**

![70][]

如：后序遍历的数组 \{5，7，6，9，11，10，8\} ，8为树的根节点 ，数组前半部分\{5，7，6\}为左子树部分，后半部分\{9，11，10\} 为右子树部分；对于数组\{5，7，6\} ,最后一个元素 6 为左子树的根节点，\{5\} 为子子树结点，\{7\}为右子树结点；数组\{9，11，10\}一样的道理。。。得到数组 \{5，7，6，9，11，10，8\} 为数的后续遍历。。

如：数组\{7，4，6，5\} 即 最后一个元素 5为树的根节点，因为第一个元素 7>5，所以7为二叉树的右子树结点，表示该树没有左子树，数组的所有元素都是右子树结点；但是第二个元素 4<5 不符合二叉树的所有右子树结点都大于根节点的条件，所以不存在这样的二叉树后续的遍历结果。。

**扩展：输入数组判读是否为前序遍历（数组的第一个元素为树的根节点）。。**

**具体代码：**

package com.test.my编程;
    
    public class Test24 {
    
    	public boolean VerifySquenceOfBST(int []array)
    	{
    		
    		if(array==null || array.length<=0)
    		{
    			return false;
    		}
    		
    		return tree(array, 0, array.length-1);
    	}
    	
    	public boolean tree(int []array ,int start,int end)
    	{
    		if(start>=end) return true;
    		
    		//后序遍历的最后一个元素是树的根节点
    		int root=array[end];
    		
    		
    		int i=start;
    		//二叉树的左子树结点都小于根节点
    		while(array[i]<root)
    		{
    			 i++; 
    		}
    		 
    		
    		 int j=i;
                    //二叉树的右子树结点都大于根节点
    		while(j<end)
    		{
    			if(array[j]<root)
    			 {
    				 return false;
    			 }
    			j++;
    		}
    		
    		//递归判左子树是不是二叉树搜索树
    		boolean left=tree(array, start, i-1);
    		
    		//递归判右子树是不是二叉树搜索树
    		boolean right=tree(array, i, end-1);
    			
    		return left && right;
    		
    	}
    
    }

[70]: /images/20220514/7571fe062ec14d6b9722219c1b89923d.png