您的位置:1010cc时时彩经典版 > 1010cc时时彩经典版 > 1010cc时时彩经典版二叉搜索树的后序遍历序列

1010cc时时彩经典版二叉搜索树的后序遍历序列

发布时间:2019-08-11 17:48编辑:1010cc时时彩经典版浏览(97)

    剑指offer面试题24:二叉搜索树的后序遍历序列,剑指offer

    题目:输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是返回true,否则返回false。 假设输入的数组任意两个数字都不相同

    解题思路:二叉搜索树的特点是根节点的左子树的值小于等于根节点的值,右子树的结点的值大于等于根节点的值。

    在二叉树的后序遍历序列中,最后一个数字是树的根节点。

    根据二叉搜索树的后序遍历特点,序列的前半部分是左子树结点的值,他们都比根的值小;后半部分是右子树结点的值,他们都比根的值大。

    package Solution;
    
    
    public class No24SequenceOfBinarySearchTree {
    
        public static void main(String[] args) {
            int[] array1 = { 5, 7, 6, 9, 11, 10, 8 };
            System.out.println(verifySequenceOfBinarySearchTree(array1, 0,
                    array1.length - 1));
            int[] array2 = { 7, 1, 6, 5 };
            System.out.println(verifySequenceOfBinarySearchTree(array2, 0,
                    array2.length - 1));
    
        }
    
        public static boolean verifySequenceOfBinarySearchTree(int[] array,
                int start, int end) {
            if (array == null || start > end || start < 0 || end < 0)
                return false;
            if (start == end)
                return true;
            int root = array[end];
            int i = start;
            for (; i < end; i  ) {
                if (array[i] > root)
                    break;
            }
            int j = i;
            for (; j <= end; j  ) {
                if (array[j] < root)
                    return false;
            }
            // 递归判断左子树是不是二叉搜索树
            boolean left = false;
            if (i > start) {
                left = verifySequenceOfBinarySearchTree(array, start, i - 1);
            }
            // 递归判断右子树是不是二叉搜索树
            boolean right = false;
            if (i < end) {
                right = verifySequenceOfBinarySearchTree(array, i, end - 1);
            }
            return left && right;
        }
    }
    

     

    题目:输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如...

    在二叉树的后序遍历序列中,最后一个数字是树的根节点。


    题目描述

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

    思路:主要是根据根节点划后序遍历数组,分出左右子树,判断左右子树和根节点值的大小是否符合二叉搜索树的大小关系,并递归判断左右子树是否为二叉搜索树。依此为依据作为判断的结果,注意left=true初始化为true,因为左子树可能为空,这样不影响判断右子树是否为二叉搜索树。

    总的来说就是,判断根节点和左右是否满足二叉搜索树的特点,然后根据后序遍历序列来分别判断左右子树是否为二叉搜索树即可,如果不是,那么返回false。

    代码如下:

    public class Solution {
        public boolean VerifySquenceOfBST(int [] sequence) {
    
            if(sequence==null || sequence.length==0){
                return false;
            }
    
            int len = sequence.length;
            return VerifySquenceOfBST(sequence,0,len-1);
    
        }
    
          public boolean VerifySquenceOfBST(int[] array,int start,int end){
    
            int root = array[end];  
            //在二叉搜索树中左子树的结点小于根节点  
            int i = start;  
            for(; i < end;i  ){  
                if(array[i]>root)  
                    break;  
            }  
            //在二叉搜索树中右子树的结点大于根节点  
            int j = i;  
            for(;j < end;j  ){  
                if(array[j] < root)  
                    return false;  
            }  
            //判断左子树是不是二叉搜索树,如果没有左子树,就相当于左子树是真,所以left初始化为true,不影响右子树的判断结果
            boolean left = true;  
            if(i >start)  
                left =VerifySquenceOfBST(array ,start,i-1);  
            //判断右子树是不是二叉搜索树,如果没有右子树,就相当于右子树是真,所以right初始化为true,不影响左子树的判断结果
            boolean right = true;  
            if(i < end)  
                right = VerifySquenceOfBST(array,i,end-1);  
            return (left && right);  
        }
    }
    

    题目:

    输入某二叉树的前序遍历和中序遍历的结果。请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如,输入的前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建如图所示的二叉树并输出它的头节点。

           1
          /  
        2     3
       /     / 
      4      5  6
               /
        7      8
    

    举一反三:要求处理一颗二叉树的遍历序列,可以先找到二叉树的根节点,在基于根节点把整棵树的遍历序列拆分成左子树对应的序列和右子树对应的序列,接下来再递归的处理这两个子序列。

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

    代码实现

    /**
     * Definition of TreeNode:
     * public class TreeNode {
     *     public int val;
     *     public TreeNode left, right;
     *     public TreeNode(int val) {
     *         this.val = val;
     *         this.left = this.right = null;
     *     }
     * }
     */
    public class Solution {
        /**
         * @param root the root of binary tree
         * @param target an integer
         * @return all valid paths
         */
       // List<List<Integer>> result = new ArrayList<>();
        public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
            List<List<Integer>> result = new ArrayList<>();
            if (root == null) {
                return result;
            }
            List<Integer> path = new ArrayList<>();
            path.add(root.val);
            dfs(root, root.val, target, path, result);
            return result;
        }
        private void dfs(TreeNode root, int sum, int target, List<Integer> path,
                        List<List<Integer>> result) {
            // meat leaf
            if (root.left == null && root.right == null) {
                if (sum == target) {
                    result.add(new ArrayList<>(path));
                }
                return;
            }
            // go left
            if (root.left != null) {
                path.add(root.left.val);
                // notdfs(root, sum root.left.val, target, path, result);
                dfs(root.left, sum root.left.val, target, path, result);
               //去掉上一次加入的节点 dfs
               path.remove(path.size()-1);
            }
            //go right 
            if (root.right != null) {
                path.add(root.right.val);
                //dfs(root, sum root.right.val, target, path, result);
                dfs(root.right, sum root.right.val, target, path, result);
                path.remove(path.size()-1);
            }
        }
    } 
    

    面试题36:二叉搜索树与双向链表

    题目:输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是返回true,否则返回false。 假设输入的数组任意两个数字都不相同

    function VerifySquenceOfBST($sequence)
    {
            // write code here
        $flag = true;
        if(count($sequence)==0){
            return false;
        }
        if(count($sequence)==1){
            return true;
        }
        else{
            $root_val = end($sequence);
            $less_max_idx = -1 ;
            $left = array();
            $right = array();
            for($i = 0;$i < count($sequence);$i  ){
                if($sequence[$i]<$root_val){
                    $less_max_idx = $i;
                }
            }
            for($i = 0;$i<count($sequence)-1;$i  ){
                if($i<=$less_max_idx){
                  $left[] = $sequence[$i];
                }else{
                   $right[] = $sequence[$i]; 
                }
            }
            //验证左子树,必须都比根节点小
            for($i =0;$i<count($left);$i  ){
                if($left[$i] > $root_val){
                    return false;
                }
            }
            for($i = 0; $i<count($right); $i  ){
                if($right[$i] < $root_val){
                    return false;
                }
            }
            if(count($left)>0){
               $flag &= VerifySquenceOfBST($left);
            }
            if($flag&&count($right)>0){ 
                $flag &= VerifySquenceOfBST($right);
            }
            return $flag;
        }
    }
    

    题目:

    设计一个算法,并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为 “序列化”,读取文件后重建同样的二叉树被称为 “反序列化”。

    如何反序列化或序列化二叉树是没有限制的,你只需要确保可以将二叉树序列化为一个字符串,并且可以将字符串反序列化为原来的树结构。

    根据二叉搜索树的后序遍历特点,序列的前半部分是左子树结点的值,他们都比根的值小;后半部分是右子树结点的值,他们都比根的值大。

    一个二叉树结构是不能仅仅根据后续遍历确定的,但是题目中的二叉树是二叉搜索树,二叉搜索树的性质是节点左子树的值一定小于根节点,右子树的值一定都大于根节点,后续遍历的顺序是先左然后右最后根节点,所以序列的最后一个元素一定是根节点。曾想过既然最后一个元素是根节点,自己能不能根据二叉搜索树的性质和给定的序列能否构建出一个搜索树呢。比如给定测试序列[4,8,6,12,16,14,10],其中10是根节点,14大于10所以14应该在10的右子树,16大于14,16位于14的右子树,12大于10小于14所以位于14的左子树...... 就这样构建,完成后然后在进行一次后序遍历然后和给定的序列进行比较是否一致。但是这样实在太麻烦了。而且题目中没有给定树的结构,说明题目不需要进行先构建二叉搜索树然后进行后序遍历再比较序列的一致性来求解。所以还是考虑二叉搜索树的性质和树的递归结构,二叉搜索树的节点除了大小性质外,每个子树同样是二叉搜索树。所以完全可以递归求解。求解思路:如果给定的序列符合,根据后续的遍历一定可以找到根节点的左子树的遍历序列和右子书的遍历序列。左边的都一定比根节点小,右边的都比根节点大,有一个不符合就返回false。如果符合就递归的求解左序列和右序列。如果每次递归都符合说明给定序列符合条件。其中遇到的一个问题是如果序列为空应该怎么判断,因为一个二叉搜索树仅仅有左子树或者右子树是可能的,所以我之前判断如果序列元素的数量小于等于1应该返回true。但是如果第一次输入给函数的时候就是空序列,显然是不应该返回true的。所以如果序列为空返回false,后面进行递归之前如果子序列为空就不递归来实现。

    样例:

        8           8          8
       /          /         /  
      6    6      6    9     7    7
     /   /     /   /    /   / 
    5   7 7  5   5 7 7   5  7 7  7
    3棵二叉树,其中第一棵是对称的,另外两棵不是
    

    解题思路:二叉搜索树的特点是根节点的左子树的值小于等于根节点的值,右子树的结点的值大于等于根节点的值。

    题目:

    给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

     

    代码实现:

    public class VerifySequenceBST {
        public static boolean verifySequenceBST(int[] seq) {
            if (seq == null || seq.length == 0) {
                return false;
            }
            return verifySequenceBST(seq, 0, seq.length-1);
        }
        private static boolean verifySequenceBST(int[] seq, int start, int end) {
            if (start > end) {
                return true;
            }
            int root = seq[end];
            //在二叉搜索树中左子树节点的值小于根节点的值
            int i = start;
            while (i < end) {
                if (seq[i] > root) {
                    break;
                }
                i  ;
            }
            //在二叉搜索树中右子树节点的值大于根节点的值
            int j =  i;
            while (j < end) {
                if (seq[j] < root) {
                    return false;
                }
                j  ;
            }
            boolean left = true;
            //判断左子树是不是二叉搜索树
            left = verifySequenceBST(seq, start, i-1);
            boolean right = true;
            //判断右子树是不是二叉搜索树
            right = verifySequenceBST(seq, i, end - 1);
            return left & right;
        }
        public static void main(String[] args) {
            int[] seq1 = {5,7,6,9,11,10,8};
            int[] seq2 = {7,4,6,5};
            System.out.println(verifySequenceBST(seq1));
            System.out.println(verifySequenceBST(seq2));
        }
    }
    

    面试题34: 二叉树中和为某一值的路径

    package Solution;
    
    
    public class No24SequenceOfBinarySearchTree {
    
        public static void main(String[] args) {
            int[] array1 = { 5, 7, 6, 9, 11, 10, 8 };
            System.out.println(verifySequenceOfBinarySearchTree(array1, 0,
                    array1.length - 1));
            int[] array2 = { 7, 1, 6, 5 };
            System.out.println(verifySequenceOfBinarySearchTree(array2, 0,
                    array2.length - 1));
    
        }
    
        public static boolean verifySequenceOfBinarySearchTree(int[] array,
                int start, int end) {
            if (array == null || start > end || start < 0 || end < 0)
                return false;
            if (start == end)
                return true;
            int root = array[end];
            int i = start;
            for (; i < end; i  ) {
                if (array[i] > root)
                    break;
            }
            int j = i;
            for (; j <= end; j  ) {
                if (array[j] < root)
                    return false;
            }
            // 递归判断左子树是不是二叉搜索树
            boolean left = false;
            if (i > start) {
                left = verifySequenceOfBinarySearchTree(array, start, i - 1);
            }
            // 递归判断右子树是不是二叉搜索树
            boolean right = false;
            if (i < end) {
                right = verifySequenceOfBinarySearchTree(array, i, end - 1);
            }
            return left && right;
        }
    }
    

    样例:

    下面的例子中 T2 是 T1 的子树:

           1                3
          /               / 
    T1 = 2   3      T2 =  4
        /
       4
    

    下面的例子中 T2 不是 T1 的子树:

           1               3
          /                
    T1 = 2   3       T2 =    4
        /
       4
    

    本文由1010cc时时彩经典版发布于1010cc时时彩经典版,转载请注明出处:1010cc时时彩经典版二叉搜索树的后序遍历序列

    关键词: