判断二叉搜素树

使用递归dfs

  1. class Solution {
  2.     public boolean isValidBST(TreeNode root) {
  3.         //深度搜索
  4.         return dfs(root,Long.MIN_VALUE,Long.MAX_VALUE);
  5.     }
  6.     public boolean dfs(TreeNode treeNode,long minValue,long maxvalue)
  7.     {
  8.         if(treeNode==null)
  9.         {
  10.             return true;
  11.         }
  12.         if(treeNode.val<=minValue||treeNode.val>=maxvalue)
  13.         {
  14.             return false;
  15.         }
  16.         return dfs(treeNode.left,minValue,treeNode.val)&&dfs(treeNode.right,treeNode.val,maxvalue);
  17.     }
  18. }

用先序遍历

  1. class Solution {
  2.     public boolean isValidBST(TreeNode root) {
  3.         //中序遍历
  4.         List<Integer> res=midleView(root);
  5.         for(int i=0;i<res.size()-1;i++)
  6.         {
  7.             if(res.get(i)>=res.get(i+1))
  8.             {
  9.                 return false;
  10.             }
  11.         }
  12.         return true;
  13.     }
  15.     public List<Integer> midleView(TreeNode root)
  16.     {
  17.         List<Integer> res=new ArrayList<>();
  18.         if(root==null)
  19.         {
  20.             return res;
  21.         }
  22.         res.addAll(midleView(root.left));
  23.         res.add(root.val);
  24.         res.addAll(midleView(root.right));
  25.         return res;
  26.     }
  27. }

对称二叉树

https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn7ihv/

dfs

二叉树 - 图1

  1. class Solution {
  2.     public boolean isSymmetric(TreeNode root) {
  3.         if(root==null)
  4.             return true;
  5.         return dfs(root.right,root.left);
  6.     }
  7.     public boolean dfs(TreeNode left,TreeNode right){
  8.         //退出条件
  9.         if(left==right&&right==null)
  10.         {
  11.             return true;
  12.         }
  13.         if(left==null||right==null||left.val==right.val)
  14.         {
  15.             return false;
  16.         }
  17.         return dfs(left.left,right.right)&&dfs(left.right,right.left);
  18.     }
  19. }

bfs

class Solution {
public boolean isSymmetric(TreeNode root) {
    //层次遍历
    List<TreeNode> list=new ArrayList<>();
    list.add(root);
    while (list.size()!=0)
    {
        for(int i=0;i<list.size()/2;i++)
        {
            if(list.get(i)==null^list.get(list.size()-1-i)==null)
            {
              return false;
            }
            if(list.get(i)==null&&list.get(list.size()-1-i)==null)
            {
                continue;
            }
            if(list.get(i).val!=list.get(list.size()-1-i).val)
            {
                return false;
            }
        }
        List<TreeNode> temp=new ArrayList<>();
        for(TreeNode treeNode:list)
        {
            if(treeNode==null)
            {
                continue;
            }
            temp.add(treeNode.left);
            temp.add(treeNode.right);
        }
        list=temp;
    }
    return true;
}
}

将有序数组转换为二叉搜索树

https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xninbt/
题中说了要转换为一棵高度平衡的二叉搜索树，并且数组又是排过序的，这就好办了，我们可以使用递归的方式，每次取数组中间的值比如m作为当前节点，m前面的值作为他左子树的结点值，m后面的值作为他右子树的节点值，示例中一个可能的结果是
二叉树 - 图2

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums,0,nums.length-1);
    }
    public TreeNode dfs(int[] nums,int i,int j)
    {
        //退出条件
        if(i>j)
            return null;
        TreeNode treeNode=new TreeNode();
        int mid=(i+j)/2;
        treeNode.val=nums[mid];
        treeNode.left=dfs(nums,i,mid-1);
        treeNode.right=dfs(nums,mid+1,j);
        return treeNode;
    }
}