力扣每日刷题

98. 验证二叉搜索树

解题思路：根据二叉搜索树的定义可得二叉树的中序遍历是一个有序数组，那么我们只要使用数组记录一下中序遍历，然后看数组是否是有序的就可以看出这棵树是不是二叉搜索树。

代码：

class Solution {
    List<Integer> list=new ArrayList<>();
    public boolean isValidBST(TreeNode root) {
        //解题思路：使用中序输出一下看看是否是有序的
        mid(root);
        for (int i = 0; i < list.size()-1; i++) {
            if(list.get(i)>=list.get(i+1)){
                return false;
            }
        }
        return true;
    }
    public void mid(TreeNode root){
        if(root==null){
            return ;
        }
        mid(root.left);
        list.add(root.val);
        mid(root.right);
    }
}

230. 二叉搜索树中第 K 小的元素

解题思路：根据二叉搜索树的定义可得二叉树的中序遍历是一个有序数组，那么我们只要使用数组记录一下中序遍历，然后获取数组中的第k个数就行了

代码：

class Solution {
    List<Integer> list=new ArrayList<>();
    public int kthSmallest(TreeNode root, int k) {
        mid(root,k);
        return list.get(k-1);
    }
    public void mid(TreeNode root,int k){
        if(root==null){
            return ;
        }
        mid(root.left,k);
        list.add(root.val);
        if(list.size()==k){
            return ;
        }
        mid(root.right,k);
    }
}

 199. 二叉树的右视图

解题思路：遍历树的时候按照根右左的顺序进行遍历，然后保存当前已经遍历过的最高的高度，如果当前节点的高度比最高的高那么就使用数组保存起来。

代码：

class Solution {
    List<Integer> list=new ArrayList<>();
    int maxh=-1;
    //遍历顺序：根右左
    public List<Integer> rightSideView(TreeNode root) {
        mid(root,0);
        return list;
    }
    public void mid(TreeNode root,int h){
        if(root==null){
            return ;
        }
        if(h>maxh){
            maxh=h;
            list.add(root.val);
        }
        mid(root.right,h+1);
        mid(root.left,h+1);
    }
}

114. 二叉树展开为链表

解题思路：消除左子树，从根节点开始每次都去寻找左子树的最右边的节点，然后把当前的右子树放到左子树的最右边的节点的右节点最后把最后把左右交换，左边赋值null，当前节点向右移动，如此循环直到所有子树被消除完。

代码：

class Solution {
    public void flatten(TreeNode root) {
        while(root!=null){
            TreeNode t=root.left;
            while(t!=null&&t.right!=null){
                t=t.right;
            }
            if(t!=null){
                t.right=root.right;
                root.right=root.left;
                root.left=null;
            }
            root=root.right;
        }
    }
}

原文地址：https://blog.csdn.net/2301_79390585/article/details/145090069

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！