二叉树的递归遍历
递归的三要素
1.递归函数的参数和返回值
2.递归出口
3.单层递归的逻辑
144. 二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
/** * 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; * } * } */ class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); preoder(root,result); return result; } public void preoder(TreeNode node,List<Integer> result){ if (node==null){ return; } result.add(node.val);//前序遍历：中、左、右 preoder(node.left,result); preoder(node.right,result); } } 94. 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
/** * 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; * } * } */ class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList(); inorder(root,result); return result; } public void inorder(TreeNode node, List<Integer> result){ if(node==null){ return; } inorder(node.left,result);//中序遍历：左、中、右 result.add(node.val); inorder(node.right,result); } } 145. 二叉树的后序遍历
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
/** * 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; * } * } */ class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new ArrayList(); postorder(root,result); return result; } public void postorder(TreeNode node,List<Integer> result){ if(node==null){ return; } postorder(node.left,result);//后序遍历：左、右、中 postorder(node.right,result); result.add(node.val); } } 二叉树的迭代遍历
用栈操作，递归也是用栈实现的嘛🙂
144. 二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
/** * 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; * } * } */ class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>();//结果列表 Stack<TreeNode> stack = new Stack<>(); if(root==null){ return result; } stack.push(root);//先把根节点加到栈中去 while (!stack.empty()){ TreeNode node = stack.pop();//从栈中弹出一个结点来进行操作 result.add(node.val);//弹出的元素加到结果列表中 if(node.right!=null){ stack.push(node.right);//右孩子不空就进栈 } if(node.left!=null){ stack.push(node.left);//左孩子不空就进栈 } } return result; } } - 妙蛙种子吃了妙脆角，妙到家啦
145. 二叉树的后序遍历
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
/** * 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; * } * } */ class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>();//结果列表 Stack<TreeNode> stack = new Stack<>(); if(root==null){ return result; } stack.push(root);//先把根节点加到栈中去 while (!stack.empty()){ TreeNode node = stack.pop();//从栈中弹出一个结点来进行操作 result.add(node.val);//弹出的元素加到结果列表中 if(node.left!=null){ stack.push(node.left);//左孩子不空就进栈 } if(node.right!=null){ stack.push(node.right);//右孩子不空就进栈 } } Collections.reverse(result); return result; } } Collections.reverse(result) 链表反转
- 这题和前序遍历十分相似，就是入栈顺序不一样，画图找一下顺序，改前序遍历的代码就可啦
94. 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
- 中序遍历和前序遍历、后序遍历不一样的地方是，前序遍历（中左右）、后序遍历（左右中），中结点在两端，处理结点就是当前遍历的结点（从根节点开始遍历，从根节点开始处理）。而中序遍历的遍历从根节点开始，要处理的结点却是从最左侧的结点开始。
/** * 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; * } * } */ class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>();//结果列表 Stack<TreeNode> stack = new Stack<>(); if(root==null){ return result; } TreeNode cur = root;//取到根结点 while (cur != null || !stack.isEmpty()){ if (cur != null){ stack.push(cur);//放入栈中 cur = cur.left;//把当前结点的左孩子赋给当前结点 }else{ cur = stack.pop();//弹出栈中的结点 result.add(cur.val);//放入结果集中 cur = cur.right;//把当前结点的右孩子赋给当前结点（左边已经遍历完了，上一步也把中间放入结果集中，该右边了） } } return result; } } 二叉树的层序遍历
也就是广度优先遍历啦
102.二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
/** * 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; * } * } */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>();//外层链表 Queue<TreeNode> que = new LinkedList<>();//新建一个队列 if (root == null) { return res; } que.add(root);//把根节点放入队列 while (!que.isEmpty()){ //当队列不为空时 ArrayList<Integer> item = new ArrayList<>();//内层链表 int size = que.size();//队列的大小 while (size>0){ TreeNode node = que.poll();//弹出当前结点 if(node.left!=null){que.add(node.left);}//把当前结点的左孩子加进去（如果有的话） if(node.right!=null){que.add(node.right);}//把当前结点的右孩子加进去（如果有的话） item.add(node.val);//当前结点加到链表 size--; } res.add(item);//内层链表加入到外层链表中 } return res; } } 下面是一堆层序遍历的题
107. 二叉树的层序遍历 II
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
/** * 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; * } * } */ class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> res = new ArrayList<>();//外层链表 Queue<TreeNode> que = new LinkedList<TreeNode>();//队列 if(root==null)return res; que.add(root);//把根结点放入队列 while (!que.isEmpty()){ List<Integer> item = new ArrayList<>(); int size = que.size(); while (size > 0) { TreeNode node = que.poll();//队列中弹出一个结点 item.add(node.val); if(node.left!=null){que.add(node.left);} if(node.right!=null){que.add(node.right);} size--; } res.add(item); } Collections.reverse(res); return res; } } 199. 二叉树的右视图
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
/** * 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; * } * } */ class Solution { public List<Integer> rightSideView(TreeNode root) { List<Integer> res = new ArrayList<>(); Queue<TreeNode> que = new LinkedList<>(); if(root==null)return res; que.add(root);//根结点不为空，放入队列 while (!que.isEmpty()){ List<Integer> item = new ArrayList<>(); int size = que.size(); while (size>0){ TreeNode node = que.poll(); item.add(node.val); if(node.left!=null){que.add(node.left);} if(node.right!=null){que.add(node.right);} size--; } Integer i = item.get(item.size() - 1); res.add(i); } return res; } } 637. 二叉树的层平均值
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
/** * 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; * } * } */ class Solution { public List<Double> averageOfLevels(TreeNode root) { List<Double> res = new ArrayList<>(); Queue<TreeNode> que = new LinkedList<>(); if(root==null)return res; que.add(root); while (!que.isEmpty()){ int size = que.size(); double x = 0; double sum = 0; int count = size; while (size>0){ TreeNode node = que.poll(); sum += node.val; if(node.left!=null){que.add(node.left);} if(node.right!=null){que.add(node.right);} size--; } x = sum/count; res.add(x); } return res; } } 429. N 叉树的层序遍历
给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
/* // Definition for a Node. class Node { public int val; public List<Node> children; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, List<Node> _children) { val = _val; children = _children; } }; */ class Solution { public List<List<Integer>> levelOrder(Node root) { List<List<Integer>> res = new ArrayList<>();//外层链表 Queue<Node> que = new LinkedList<>();//新建一个队列 if (root == null) { return res; } que.add(root);//把根节点放入队列 while (!que.isEmpty()){ //当队列不为空时 ArrayList<Integer> item = new ArrayList<>();//内层链表 int size = que.size();//队列的大小 while (size>0){ Node node = que.poll();//弹出当前结点 //当前结点加到链表 if(node.children!=null){ for (Node child : node.children) { que.add(child); } } item.add(node.val); size--; } res.add(item);//内层链表加入到外层链表中 } return res; } } - 添加子结点到队列的操作有点不一样
515. 在每个树行中找最大值
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
/** * 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; * } * } */ class Solution { public List<Integer> largestValues(TreeNode root) { List<Integer> res = new ArrayList<>(); Queue<TreeNode> que = new LinkedList<>(); if(root==null){ return res; } que.add(root); while(!que.isEmpty()){ int size = que.size(); int x = Integer.MIN_VALUE; while(size>0){ TreeNode node = que.poll(); x = node.val>x ? node.val : x; if(node.left!=null){que.add(node.left);} if(node.right!=null){que.add(node.right);} size--; } res.add(x); } return res; } } 116. 填充每个节点的下一个右侧节点指针
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
/* // Definition for a Node. class Node { public int val; public Node left; public Node right; public Node next; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, Node _left, Node _right, Node _next) { val = _val; left = _left; right = _right; next = _next; } }; */ class Solution { public Node connect(Node root) { Queue<Node> que = new LinkedList<>(); if (root == null) { return root; } que.add(root); while (que.size() > 0) { int size = que.size(); Node node = que.poll(); if (node.left != null) {que.add(node.left);} if (node.right != null) {que.add(node.right);} for (int i = 1; i < size; i++) { Node next = que.poll();//弹出该层剩余元素 if (next.left != null) que.add(next.left); if (next.right != null) que.add(next.right); node.next = next; node = next; } } return root; } } 117. 填充每个节点的下一个右侧节点指针 II
给定一个二叉树
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
/* // Definition for a Node. class Node { public int val; public Node left; public Node right; public Node next; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, Node _left, Node _right, Node _next) { val = _val; left = _left; right = _right; next = _next; } }; */ class Solution { public Node connect(Node root) { Queue<Node> que = new LinkedList<>(); if (root == null) { return root; } que.add(root); while (que.size() > 0) { int size = que.size(); Node node = que.poll(); if (node.left != null) {que.add(node.left);} if (node.right != null) {que.add(node.right);} for (int i = 1; i < size; i++) { Node next = que.poll();//弹出该层剩余元素 if (next.left != null) que.add(next.left); if (next.right != null) que.add(next.right); node.next = next; node = next; } } return root; } } - 离大谱，这题代码跟上题一样，一模一样
104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
/** * 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; * } * } */ class Solution { public int maxDepth(TreeNode root) { Queue<TreeNode> que = new LinkedList<>();//新建一个队列 if (root == null) { return 0; } que.add(root);//把根节点放入队列 int count = 0; while (!que.isEmpty()) { //当队列不为空时 count++; ArrayList<Integer> item = new ArrayList<>();//内层链表 int size = que.size();//队列的大小 while (size > 0) { TreeNode node = que.poll();//弹出当前结点 if (node.left != null) { que.add(node.left); }//把当前结点的左孩子加进去（如果有的话） if (node.right != null) { que.add(node.right); }//把当前结点的右孩子加进去（如果有的话） size--; } } return count; } } 111. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
/** * 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; * } * } */ class Solution { public int minDepth(TreeNode root) { Queue<TreeNode> que = new LinkedList<>();//新建一个队列 if (root == null) { return 0; } que.add(root);//把根节点放入队列 int count = 0; while (!que.isEmpty()) { //当队列不为空时 count++; ArrayList<Integer> item = new ArrayList<>();//内层链表 int size = que.size();//队列的大小 while (size > 0) { TreeNode node = que.poll();//弹出当前结点 if (node.left != null) { que.add(node.left); }//把当前结点的左孩子加进去（如果有的话） if (node.right != null) { que.add(node.right); }//把当前结点的右孩子加进去（如果有的话） if(node.left==null&&node.right==null){ return count; } size--; } } return count; } } 总结
-
通过今天的题目大致掌握二叉树的结构。深度优先遍历方面掌握前序、中序、后续的递归实现和迭代实现。掌握广度优先遍历的模板（写了十道层序遍历的题目，就算是小猪也会了😐
-
今天的题目自己写出来的不多，除了最后几道改模板的题，不知道是因为天太冷还是头上戴的蝴蝶结封印了我的智慧的🙃
