假设我们的二叉树长这个样子
先定义一下我们的节点
@Data public class TreeNode { int val; //左子树 TreeNode left; //右子树 TreeNode right; //构造方法 TreeNode(int x) { val = x; } }
二叉树的遍历
遍历其实就是把二叉树所有的节点都过一遍，不管是前/中/后，主语都是根结点
前序遍历
前序遍历，指的是根结点的前序遍历，也就是，根→左→右
// 递归先序遍历 public static void traversal(TreeNode root) { if (root != null) { System.out.print(root.val + " "); traversal(root.left); traversal(root.right); } }
中序遍历
中序遍历，指的是根结点的中序遍历，也就是，左→根→右
// 递归中序遍历 public static void traversal(TreeNode root) { if (root != null) { traversal(root.left); System.out.print(root.val + " "); traversal(root.right); } }
后序遍历
后序遍历，指的是根结点的后序遍历，也就是，左→右→根
// 递归后序遍历 public static void traversal(TreeNode root) { if (root != null) { traversal(root.left); traversal(root.right); System.out.print(root.val + " "); } }
深度优先遍历DFS
深度优先遍历=前/中/后序遍历
//非递归 public void traverse(TreeNode root){ if (root==null){ return; } LinkedList<TreeNode> stack=new LinkedList<>(); //放进去 stack.push(root); while (!stack.isEmpty()){ //取出来 TreeNode node=stack.pop(); System.out.println(node.val+" "); //因为栈是先进后出，所以先放右节点 if (node.right!=null){ //右节点不空，放右节点 stack.push(node.right); } if (node.left!=null){ //左节点不空，放左节点 stack.push(node.left); } } }
广度优先遍历BFS
对二叉树来说，广度优先=层级遍历
层级遍历
顾名思义，一层一层的遍历
//层级遍历 public static void levelTraverse(TreeNode root){ if (root==null){ return; } LinkedList<TreeNode> queue=new LinkedList<>(); //放到尾巴上 //Adds the specified element as the tail (last element) of this list. queue.offer(root); while (!queue.isEmpty()){ //Retrieves and removes the head (first element) of this list. //将第一个弹出来 TreeNode node=queue.poll(); System.out.println(node.val+" "); //因为队列是先进先出，所以先放左节点 if (node.left!=null){ //左节点不空，放左节点 queue.offer(node.left); } if (node.right!=null){ //右节点不空，放右节点 queue.offer(node.right); } } }
深度
二叉树的深度
// 树的深度 public static int deep(TreeNode root) { if (root != null) { return 0; } return Math.max(deep(root.left),deep(root.right))+1; }
二叉搜索/查找树
二叉查找树（BST：Binary Search Tree）是一种特殊的二叉树，它改善了二叉树节点查找的效率。二叉查找树有以下性质：
对于任意一个节点 n，
- 其左子树（left subtree）下的每个后代节点（descendant node）的值都小于节点 n 的值；
- 其右子树（right subtree）下的每个后代节点的值都大于节点 n 的值。
构建
比如给出[7,8,12]，要求构建二叉搜索树
//构建二叉搜索树 public TreeNode sortedArrayToBST(int[] nums) { return nums=null?null:bulidTree(nums,0,nums.length-1); } private TreeNode bulidTree(int[] nums, int l, int r) { if(l>r){ return null; } int m=l+(r-l)/2; TreeNode root =new TreeNode(nums[m]); root.left=bulidTree(nums,l,m-1); root.right=bulidTree(nums,m+1,r); return root; }
验证
也是通过遍历实现，比二叉树多一步卡边界值的操作
//二叉搜索树的验证 public boolean isValidBST(TreeNode root) { long min=Long.MIN_VALUE; long max=Long.MAX_VALUE; return validBST(root,min,max); } public boolean validBST(TreeNode root,long min,long max){ if (root==null){ return true; } if (min>=root.val||max<=root.val){ return false; } return validBST(root.left,min,root.val)&&validBST(root.right,root.val,max); }
查找
查找比较简单，就是判断
//二叉搜索树的查找 public TreeNode searchBST(TreeNode root, int val) { if(root==null||root.val==val){ return root; } return root.val > val ? searchBST(root.left,val):searchBST(root.right,val); }
