LeetCode 对称二叉树/验证二叉搜索树-一一网

这是我参与更文挑战的第 24 天，活动详情查看：更文挑战

对称二叉树（101）

题目描述

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

示例 1：

    1
   / \
  2   2
 / \ / \
3  4 4  3
复制代码

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

进阶：

你可以运用递归和迭代两种方法解决这个问题吗？

思路分析

验证是不是对称二叉树，也就是说对应的点上的点是相等的，我们可以用一个队列进行处理，如果是对称的，那么最左边的节点和最右边的节点是相等的，然后再不断的变量每个节点，直到队列为空。

第二种解法是弄两个节点，然后左边的节点和对应右边的节点相等，直到结束。

代码展示

解法一：

public boolean isSymmetric(TreeNode root) {
        return check(root,root);
    }

    private boolean check(TreeNode p,TreeNode q){
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(p);
        queue.offer(q);
        while(!queue.isEmpty()){
            p = queue.poll();
            q = queue.poll();

            if(p == null && q == null){
                continue;
            }
            if(p == null || q == null){
                return false;
            }
            if(p.val != q.val){
                return false;
            }
            queue.offer(p.left);
            queue.offer(q.right);

            queue.offer(p.right);
            queue.offer(q.left);
        }
        return true;


    }
复制代码

解法二：

    public boolean isSymmetric(TreeNode root) {
        return check(root,root);
    }

    private boolean check(TreeNode p,TreeNode q){
        if(p == null && q == null){
            return true;
        }
        if(p == null || q == null){
            return false;
        }
        return p.val == q.val && check(p.left,q.right) && check(p.right,q.left);
    }
复制代码

验证二叉搜索树（98）

题目描述

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入:
    2
   / \
  1   3
输出: true
复制代码

示例 2：

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。
复制代码

思路分析

验证二叉搜索树，我们可以看到前面二叉搜索树的特点，节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。同时我们前面也学过二叉树的前中后序遍历，结合二叉树搜索树的特点，我们可以通过二叉树的中序遍历，如果是二叉搜索树，那么中序遍历就是从小到大，我们中序遍历完，再判断是不是从小到大。

代码展示

解法一：

public boolean isValidBST(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorder(root,result);
        for(int i = 0;i < result.size()-1;i++){
            if(result.get(i) >= result.get(i+1)){
                return false;
            }
        }
        return true;
    }

    private void inorder(TreeNode node,List<Integer> result){
        // if(node == null){
        //     return;
        // }
        // inorder(node.left,result);
        // result.add(node.val);
        // inorder(node.right,result);

        Stack<TreeNode> stack = new Stack<>();
        while(!stack.isEmpty() || node != null){
            
            while(node != null){
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            result.add(node.val);
            node = node.right;
        }
    }
复制代码