Hot100——二叉树

树的定义：

    public static class TreeNode{int val;TreeNode left;TreeNode right;TreeNode(){};TreeNode(int val){ this.val = val; };TreeNode(int val, TreeNode left, TreeNode right){this.val = val;this.left = left;this.right = right;}}

深度优先遍历（DFS）（使用递归，底层是栈）：

class Solution {public List<Integer> inorderTraversal(TreeNode root) {//中序遍历LinkedList result = new LinkedList<Integer>();inorder(root, result);return result;}//前序遍历public void preorder(TreeNode root, List<Integer> result){if(root == null){ return;}//中左右result.add(root.val);preorder(root.left, result);preorder(root.right, result);}//中序遍历public void inorder(TreeNode root, List<Integer> result){if(root == null){ return;}//左中右inorder(root.left, result);result.add(root.val);inorder(root.right, result);}//后序遍历public void postorder(TreeNode root, List<Integer> result){if(root == null){ return;}//左右中postorder(root.left, result);postorder(root.right, result);result.add(root.val);}
}

广度优先遍历（BFS）（底层是队列，可以解决最大深度等问题）：

    /*底层是队列，记录每一层的元素个数，把每一层的值都加入队列先add node再加入左右子树。循环条件为队列非空。*/public List<List<Integer>> BFS_Impl(TreeNode node){//以queue的方式遍历，先入先出，值存储在List中Queue<TreeNode> queue = new LinkedList<TreeNode>();//遍历结果存储在list中List<List<Integer>> res = new LinkedList<List<Integer>>();if (node == null){return res;}queue.add(node);while (!queue.isEmpty()){int size = queue.size();List<Integer> List = new ArrayList<>();for (int i=0; i < size; i++){TreeNode current = queue.poll();//每次从队列中取出一个节点List.add(current.val);// 添加当前节点的值到当前层级列表if (current.left != null){queue.add(current.left);//左子节点入队}if (current.right != null){queue.add(current.right);//右子节点入队}}res.add(List);}return res;}

104. 二叉树的最大深度 - 力扣（LeetCode）

class Solution {public int maxDepth(TreeNode root) {if (root == null){return 0;}//按照层序遍历的方式遍历二叉树，返回List的长度即为深度Queue<TreeNode> queue = new LinkedList<>();List<List<Integer>> result = new LinkedList<>();queue.add(root);while (! queue.isEmpty()){List<Integer> List = new LinkedList();int size = queue.size();for (int i=0; i<size; i++){TreeNode node = queue.poll();List.add(node.val);if(node.left != null){queue.add(node.left);}if(node.right != null){queue.add(node.right);}}            result.add(List);}int max = result.size();return max;}
}