897-递增顺序查找树

AndroidTraveler 发布于2019-08-19 11:05 / 929人阅读

摘要：前言的递增顺序查找树，题目要求如下给定一个树，按顺序重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。

前言

Weekly Contest 100的递增顺序查找树，题目要求如下：

给定一个树，按顺序重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。

示例：

输入：[5,3,6,2,4,null,8,1,null,null,null,7,9]

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

输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

 1
  
   2
    
     3
      
       4
        
         5
          
           6
            
             7
              
               8
                
                 9

解题思路

这道题解题步骤如下：

找出树的最左节点：用中序遍历的方式获取到树的最左节点的访问序列

根据这个访问序列生成一个只有右节点的树即可

PS:我个人是把中序遍历简单记做左中右

实现代码

/**
  * 递增顺序查找树
  *
  * @param root
  * @return
  */
 public TreeNode increasingBST(TreeNode root) {
     List list = inorderTraversal(root);
     TreeNode result = new TreeNode(list.get(0));
     TreeNode currentNode = result;
     for (int i = 1; i < list.size(); i++) {
         currentNode.right = new TreeNode(list.get(i));
         currentNode = currentNode.right;
     }
     return result;
 }
 
 /**
  * 中序遍历
  * @param root
  * @return
  */
 private List inorderTraversal(TreeNode root) {
     List list=new ArrayList();
     if(root!=null){
         inorderTraversal(root,list);
     }
     return list;
 }

 /**
  * 中序遍历时调用的递归方法
  * @param root
  * @return
  */
 private void inorderTraversal(TreeNode root,List list){
     if(root.left!=null){//遍历左子树
         inorderTraversal(root.left,list);
     }
     list.add(root.val);//记录根节点
     if(root.right!=null){//遍历右子树
         inorderTraversal(root.right,list);
     }
 }

idc机房托管专线服务顺序查找c语言二叉查找树二叉查找树删除结点自递增

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/76967.html

⭐算法入门⭐《二叉树 - 二叉搜索树》简单05 —— LeetCode 897. 递增顺序搜索树

文章目录一、题目1、题目描述2、基础框架3、原题链接二、解题报告1、思路分析2、时间复杂度3、代码详解三、本题小知识四、加群须知一、题目 1、题目描述给你一棵二叉搜索树，请按中序遍历将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。样例输入： [5,3,6,2,4,null,8,1,null,null,nu...

Soarkey 2021-09-10 10:51 评论0 收藏0
leetcode98. Validate Binary Search Tree

摘要：题目要求检验二叉查找树是否符合规则。二叉查找树是指当前节点左子树上的值均比其小，右子树上的值均比起大。因此在这里我们采用栈的方式实现中序遍历，通过研究中序遍历是否递增来判断二叉查找树是否符合规则。题目要求 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is...

codercao 2019-08-15 10:56 评论0 收藏0
leetcode98. Validate Binary Search Tree

摘要：题目要求检验二叉查找树是否符合规则。二叉查找树是指当前节点左子树上的值均比其小，右子树上的值均比起大。因此在这里我们采用栈的方式实现中序遍历，通过研究中序遍历是否递增来判断二叉查找树是否符合规则。题目要求 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is...

AlphaWatch 2019-08-15 10:56 评论0 收藏0
查找算法——JS算法实现

摘要：查找表查找表相关概念查找表是由同一类型的数据元素或记录构成的集合。由于集合中的数据元素之间存在着完全松散的关系，因此查找表是一种非常灵便的数据结构。缺点平均查找长度较大。索引顺序表的查找若以索引顺序表表示静态查找表，则查找可以用分块查找。查找表 search table 查找表相关概念查找表是由同一类型的数据元素(或记录)构成的集合。由于集合中的数据元素之间存在着完全松散的关系，因...

sihai 2019-08-22 11:01 评论0 收藏0