二叉树的定义
- 跟链表的定义方式比较像
class BinaryNode<AnyType> { AnyType element; // The data in the node BinaryNode<AnyType> left; // Left child BinaryNode<AnyType> right; // right child public BinaryNOode(AnyType element) { this(element,null,null); } public BinaryNOode(AnyType element, BinaryNode<AnyType> left,BinaryNode<AnyType> right) { this.element = element; this.right = right; this.left = left; } }
// Definition for a binary tree node. public 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; } }
二叉树的遍历
深度优先遍历
前、中、后序递归遍历(递归法)
递归三部曲：
1、确定递归函数的参数和返回值
2、确定终止条件
3、确定单层递归的逻辑
144.二叉树的前序遍历(递归)
// 前序遍历·递归 class Solution { public List<Integer> preorderTraversal(TreeNode root) { // 创建返回值 List<Integer> result = new ArrayList<>(); preorder(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); } }
94.二叉树的中序遍历(递归)
class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); inOrder(root,result); return 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); } }
145.二叉树的后序遍历(递归)
class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); postOrder(root,result); return 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); } }
前、中、后序迭代遍历(迭代法)
迭代法的操作主要分为两步：
1、访问节点
2、处理节点
144.二叉树的前序遍历(迭代)
前序遍历时中左右，所以我们希望节点从栈中弹出来的时候也是中左右。
上图是对一个二叉树的代码模拟，画一遍更有感觉，其实循环中每次都是父节点被弹出添加，然后临走前将右节点和左节点添加进去，后面就按照左右的顺序出战
class Solution { public List<Integer> preorderTraversal(TreeNode root) { // 创建接收集合 List<Integer> result = new ArrayList<>(); // 防止空树 if (root == null) { return result; } // 创建栈 Deque<TreeNode> stack = new LinkedList<>(); // 首先先将根节点压栈 stack.push(root); // 迭代操作 while (!stack.isEmpty()) { // 获取栈顶元素 TreeNode node = stack.peek(); // 将栈顶元素弹出，并添加到集合中 result.add(stack.pop().val); // 获取节点的右子树，因为后弹出的要先压入 if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } return result; } }
145.二叉树的后序遍历(迭代)
前序遍历的代码完成之后，如果将循环中先访问右节点再访问左节点，变换成先访问左节点再访问右节点，这样对二叉树的遍历顺序就成了 中->右->左 了，这样刚好是后序遍历的倒序，那么将最后获取到的数组反转就是后序遍历了
class Solution { public List<Integer> postorderTraversal(TreeNode root) { // 创建接收集合 List<Integer> result = new ArrayList<>(); if (root == null) { return result; } // 创建栈 Deque<TreeNode> stack = new LinkedList<>(); // 首先先将根节点压栈 stack.push(root); // 迭代操作 while (!stack.isEmpty()) { // 获取栈顶元素，一会要拿着这个元素判断它的左右子树 TreeNode node = stack.peek(); // 将栈顶元素弹出，并添加到集合中 result.add(stack.pop().val); // 压入节点的左子树，因为后弹出的要先压入 if (node.left != null) { stack.push(node.left); } // 再压入节点的右子树 if (node.right != null) { stack.push(node.right); } } // 至此 集合中保存的其实是 中->右->左的遍历顺序 // 将遍历到的结果反转过来就是 左->右->中的遍历顺序了 Collections.reverse(result); return result; } }
94.二叉树的中序遍历(迭代)
在迭代代码的时候会分两步进行操作：
1、对节点的访问：遍历节点
2、对节点的处理：将节点中的val添加到数组中
前序遍历的顺序是中左右，我们是从根节点(中间节点)入手的，访问到了根节点之后就对根节点进行了处理
但是中序遍历的顺序是左中右，先访问的是根节点(中间节点)，访问到了中间节点之后不能对中间节点进行处理，而是要继续向左子树访问，一层一层下去，知道最左边的元素，再开始对节点进行处理
所以前面只能访问，不能处理
那就只能借助指针进行访问，访问到目的元素之后再进行处理
访问：从根节点开始一路向左进行访问，只要左子树有节点，那就进行压栈，其实压的这些都是“中”
处理：当访问的节点的左侧再没有节点的时候，将栈中的栈顶弹出，再去访问弹出节点的右子树
class Solution { public List<Integer> inorderTraversal(TreeNode root) { // 创建接收数组 List<Integer> result = new ArrayList<>(); if (root == null) { return result; } // 创建栈 Deque<TreeNode> stack = new ArrayDeque<>(); // 创建指针 TreeNode cur = root; while (cur != null || !stack.isEmpty()) { if (cur != null) { // 如果节点不是空，那就将节点添加到栈中，继续寻找左孩子 stack.push(cur); cur = cur.left; } else { // 如果节点为空了，那就说明没有左孩子了，压进去的节点可以弹出了，然后去看弹出节点的右孩子 TreeNode node = stack.pop(); result.add(node.val); cur = node.right; } } return result; } }
前、中、后序统一迭代
统一迭代法的书写风格，待定学习
广度优先遍历
二叉树的层序遍历
120.二叉树的层序遍历 力扣
层序遍历真的是思路简单，代码舒适呀。顾名思义，层序遍历就是对二叉树的每一层从左到右进行遍历
层序遍历需要借助队列来实现遍历，队列是先进先出，适合层序遍历的逻辑
有几个需要注意的点：
1、先将根节点入队，这样在进入循环，根据根节点开始进入循环
2、每次循环第一步，就是要判断这一层有几个节点，也就是队列的长度，获取当下的固定值，是一会要出队的个数
3、每次出一个节点，就把它的左孩子节点和右孩子节点添加进去
class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) { return result; } // 创建队列 Deque<TreeNode> queue = new ArrayDeque<>(); // 先将根节点添加进队列 queue.offer(root); while (!queue.isEmpty()) { // 获取次数队列的长度，这代表着这一层有几个节点，是一会出队的界限 int size = queue.size(); List<Integer> temp = new ArrayList<>(); while (size-- > 0) { TreeNode node = queue.poll(); temp.add(node.val); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } result.add(temp); } return result; } }
