给你一个二叉树的根节点 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！！！ }
