二叉树编程题集合(leetcode)

如果你不相信努力和时光,那么成果就会是第一个选择辜负你的。不要去否定你自己的过去,也不要用你的过去牵扯你现在的努力和对未来的展望。不是因为拥有希望你才去努力,而是去努力了,你才有可能看到希望的光芒。二叉树编程题集合(leetcode),希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

给你一个二叉树的根节点 root , 检查它是否轴对称。

首先我起先的思路是非递归用中序遍历二叉树,把每个结点的数值存在一个栈和队列中,然后判断是否回文来判断是否是对称的,但是存在一个问题那就是root = [1,2,2,null,3,null,3]会被判断为正确,后采用递归的方法

public boolean isSymmetric(TreeNode root) {
        if(root==null) {
            return true;
        }
        //调用递归函数,比较左节点,右节点
        return dfs(root.left,root.right);
    }
    
    boolean dfs(TreeNode left, TreeNode right) {
        //递归的终止条件是两个节点都为空
        //或者两个节点中有一个为空
        //或者两个节点的值不相等
        if(left==null && right==null) {
            return true;
        }
        if(left==null || right==null) {
            return false;
        }
        if(left.val!=right.val) {
            return false;
        }
        //再递归的比较 左节点的左孩子 和 右节点的右孩子
        //以及比较  左节点的右孩子 和 右节点的左孩子
        return dfs(left.left,right.right) && dfs(left.right,right.left);
    }

给定一个二叉树,找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明:叶子节点是指没有子节点的节点。

 public int minDepth(TreeNode root) {
       if(root==null)
          return 0;
       if(root.left==null&&root.right==null)
           return 1;
        int m = minDepth(root.right);
        int n=minDepth(root.left);
        if(root.left==null||root.right==null)
            return m+n+1;
        return Math.min(m+1,n+1);

    }

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下:

节点的左子树只包含 小于 当前节点的数。

节点的右子树只包含 大于 当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

  long predit = Long.MIN_VALUE;    public boolean isValidBST(TreeNode root) {        if(root==null)            return true;        else {            boolean b = isValidBST(root.left);            if(b==false||predit>=root.val)                return false;            predit=root.val;            return isValidBST(root.right);        }    }

给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

 public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<List<Integer>>();
        if (root == null) {
            return ans;
        }

        Queue<TreeNode> nodeQueue = new ArrayDeque<TreeNode>();
        nodeQueue.offer(root);
        boolean isOrderLeft = true;

        while (!nodeQueue.isEmpty()) {
            Deque<Integer> levelList = new LinkedList<Integer>();
            int size = nodeQueue.size();
            for (int i = 0; i < size; ++i) {
                TreeNode curNode = nodeQueue.poll();
                if (isOrderLeft) {
                    levelList.offerLast(curNode.val);
                } else {
                    levelList.offerFirst(curNode.val);
                }
                if (curNode.left != null) {
                    nodeQueue.offer(curNode.left);
                }
                if (curNode.right != null) {
                    nodeQueue.offer(curNode.right);
                }
            }
            ans.add(new LinkedList<Integer>(levelList));
            isOrderLeft = !isOrderLeft;
        }

        return ans;
    }

给你二叉树的根节点 root ,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

 public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> list=new ArrayList<>();
        if(root==null)
            return list;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        Stack<List<Integer>> stack=new Stack<>();
        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list1=new ArrayList<>();
            for(int i=0;i<size;i++){
                TreeNode poll = queue.poll();
                list1.add(poll.val);
                if(poll.left!=null)
                    queue.add(poll.left);
                if(poll.right!=null)
                    queue.add(poll.right);
            }
            stack.push(list1);
        }
        while (!stack.isEmpty()){
            List<Integer> pop = stack.pop();
            list.add(pop);
        }
        return list;
    }

给定一个二叉树,判断它是否是高度平衡的二叉树。

     public int maxDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);
        if(leftHeight>=0 && rightHeight>=0 && Math.abs(leftHeight-rightHeight)<=1){    //1
            return Math.max(leftHeight,rightHeight) + 1;
        }else{
            return -1;    
        }
    }
    public boolean isBalanced(TreeNode root){
        if(root == null){
            return true;
        }
        return maxDepth(root)>=0;            //非平衡树只会返回-1!!!
    }

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/197031.html

(0)
飞熊的头像飞熊bm

相关推荐

发表回复

登录后才能评论
极客之音——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!