目录
1. 二叉树的前序遍历
题目链接：二叉树的前序遍历_牛客题霸_牛客网 (nowcoder.com)
题目要求：
题目分析：
二叉树的前序遍历. 根左右
这里需要返回的是一个数组,如果直接用数组保存结点值的话,不好放进去,而且数组大小也不好直接写出.
最好的是可以用一个 List数组 add放, 最后转移到数组中去
上代码
import java.util.*;
public class Solution {
public int[] preorderTraversal (TreeNode root) {
List<Integer> list = new ArrayList<>();
preOrder(list, root);
int[] arr = new int[list.size()];
for(int i = 0; i < arr.length; i++) {
arr[i] = list.get(i);
}
return arr;
}
private void preOrder(List<Integer> list,TreeNode root) {
if(root == null) {
return;
}
list.add(root.val);
preOrder(list,root.left);
preOrder(list,root.right);
}
}2. 二叉树的中序遍历
题目链接：二叉树的中序遍历_牛客题霸_牛客网 (nowcoder.com)
题目要求：
题目分析：
和前序遍历类似,将每个结点的 val 放入 list 中, 中序遍历是 左 根 右
最后转移到 数组中返回
上代码
import java.util.*;
public class Solution {
public int[] inorderTraversal (TreeNode root) {
List<Integer> list = new ArrayList<>();
inorder(root,list);
int[] arr = new int[list.size()];
for(int i = 0; i < arr.length; i++) {
arr[i] = list.get(i);
}
return arr;
}
private void inorder(TreeNode root,List<Integer> list) {
if(root == null) {
return;
}
inorder(root.left,list);
list.add(root.val);
inorder(root.right,list);
}
}3. 二叉树的后序遍历
题目链接：二叉树的后序遍历_牛客题霸_牛客网 (nowcoder.com)
题目要求：
上代码
import java.util.*;
public class Solution {
public int[] postorderTraversal (TreeNode root) {
List<Integer> list = new ArrayList<>();
postorder(root,list);
int[] arr = new int[list.size()];
for(int i = 0; i < arr.length; i++) {
arr[i] = list.get(i);
}
return arr;
}
private void postorder(TreeNode root,List<Integer> list) {
if(root == null) {
return;
}
postorder(root.left,list);
postorder(root.right,list);
list.add(root.val);
}
}4. 求二叉树的层序遍历
题目链接：求二叉树的层序遍历_牛客题霸_牛客网 (nowcoder.com)
题目要求：
题目分析：
层序遍历,首先考虑的是用队列来做
具体的思考流程,写代码的步骤如下:
- 先创建一个队列,将根节点入队, 然后出队,在出队过程中,把节点的左右子树结点入队
- 但是现在题目中的要求是返回一个 类似于二维数组的ArrayList结构, 也就是要确定二叉树中每一层结点的个数, 每一层结点的个数也就是 队列元素的个数
- 可以再创建一个ArrayList数组,用来放每一层的结点, 前面已经确定了每层结点的个数, 所以可以写一个for循环根据每层元素个数, 出队,并把当前节点的左右子树结点入队, 当把这层结点的元素出队完,此时队列中元素的个数,也就是下一层结点的个数
- 最后要注意的是,在上一步 for 循环中, 把出队的元素要保存到用来存放每层结点的 ArrayList 中,当 for 循环完毕,也就是这层遍历完成了,就要将这个ArrayList 数组放在二维数组的一层中, 当队列为空时,意味着层序遍历完成, 那就返回二维数组
上代码
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
//根节点入队
queue.add(root);
while(!queue.isEmpty()) {
//一层的结果
ArrayList<Integer> level = new ArrayList<>();
int levelCount = queue.size();//每一层的数量
//添加一层节点到List中
for(int i = 0; i < levelCount; i++) {
//节点出队
TreeNode node = queue.remove();
//节点的左子树入队
if(node.left != null) {
queue.add(node.left);
}
//节点的右子树入队
if(node.right != null) {
queue.add(node.right);
}
level.add(node.val);
}
res.add(level);
}
return res;
}
}
5. 按之字形顺序打印二叉树
题目链接：按之字形顺序打印二叉树_牛客题霸_牛客网 (nowcoder.com)
题目要求：
题目分析：
正常的层序遍历中遍历的每一行都是从左到右的, 而这道题是一行从左到右,一行从右到左,
具体的做法和上一题一样,都是用队列的,每遍历到一行就放入到二维数组中, 不同的是因为每行的遍历顺序是交叉相反的,
所以可以定义一个变量用来标识当前队列遍历到这样层的状态
比如定义个 ret = false 队列每遍历完一行就取 !ret,如果当前ret是 true就正常放入二维数组中,如果当前 ret 是 false 就用 Collections.reverse(队列遍历到的这一层) 反转保存这一行数据的list
上代码
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(pRoot == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
//根节点入队
queue.add(pRoot);
boolean ret = true;
while(!queue.isEmpty()) {
//每一层的结点
ArrayList<Integer> arr = new ArrayList<>();
int size = queue.size();
ret = !ret;
for(int i = 0; i < size; i++) {
//节点出队
TreeNode node = queue.remove();
//左子树入队
if(node.left != null) {
queue.add(node.left);
}
//右子树入队
if(node.right != null) {
queue.add(node.right);
}
arr.add(node.val);
}
if(ret) {
Collections.reverse(arr);
}
res.add(arr);
}
return res;
}
}
6. 二叉树的最大深度
题目链接：二叉树的最大深度_牛客题霸_牛客网 (nowcoder.com)
题目要求：
题目分析：
这道题最简单的代码就是用递归来做,
往下遍历左子树和右子树,每遍历到一层就+1,找到遍历最深的那个
上代码
import java.util.*;
public class Solution {
public int maxDepth (TreeNode root) {
if(root == null) {
return 0;
}
return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}
}也可以用层序遍历来做
上一题是层序遍历二叉树,遍历完每一层然后返回给二维数组,然后打印出来
这道题如果用层序遍历来做的话,还是考虑使用队列,不过这道题只需要定义一个变量count,每遍历完一层就 count++,最后层序遍历完成,返回count
public int maxDepth (TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
if (root == null) {
return 0;
}
int count = 0;
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.remove();
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
count++;
}
return count;
}7. 二叉树中和为某一值的路径(一)
题目链接：二叉树中和为某一值的路径(一)_牛客题霸_牛客网 (nowcoder.com)
题目要求：
题目分析：
(1) 递归
上代码
import java.util.*;
public class Solution {
public boolean hasPathSum (TreeNode root, int sum) {
if(root == null) {
return false;
}
if(root.left == null && root.right == null && sum - root.val == 0) {
return true;
}
return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val);
}
}(2) 栈 + DFS
import java.util.*;
public class Solution {
public boolean hasPathSum (TreeNode root, int sum) {
if(root == null) {
return false;
}
Stack<TreeNode> s1 = new Stack<>();
Stack<Integer> s2 = new Stack<>();
s1.add(root);
s2.add(root.val);
while(!s1.isEmpty()) {
TreeNode node = s1.pop();
int sum_ret = s2.pop();
if(node.left == null && node.right == null && sum_ret == sum) {
return true;
}
if(node.left != null) {
s1.add(node.left);
s2.add(node.left.val + sum_ret);
}
if(node.right != null) {
s1.add(node.right);
s2.add(node.right.val + sum_ret);
}
}
return false;
}
}8. 二叉搜索树与双向链表
题目链接: 二叉搜索树与双向链表_牛客题霸_牛客网 (nowcoder.com)
题目要求:
题目分析:
(1) 递归+中序遍历
- 创建两个指针, head 头指针, pre 指向当前节点的前一个节点
- 中序遍历就要先递归到最左,然后当 pre为 null 时就初始化 head 和 pre
- 下面就是处理中间结点了,因为是双向链表,并且pre表示当前节点的前一个节点,这样就可以让 pre,right = 当前节点, 当前节点.left = pre, 最后再把 pre 更新为当结点
- 最后递归进入右子树
- 递归结束条件就是结点为null
上代码
public class Solution {
TreeNode head = null;
TreeNode pre = null;
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null) {
return null;
}
Convert(pRootOfTree.left);
if(pre == null) {
head = pRootOfTree;
pre = pRootOfTree;
} else {
pre.right = pRootOfTree;
pRootOfTree.left = pre;
pre = pRootOfTree;
}
Convert(pRootOfTree.right);
return head;
}
}(2) 栈 + 中序遍历
- 创建 head为头, pre 表示当前节点的前一个节点 , 创建一个标志位如果第一次到达最左端,那就为true,否则为false
- 判断树为 null 的情况
- 创建一个栈, 依次先把左结点加入到栈中,直到此时二叉树遍历到最左节点停下,此时出栈,出栈的这个节点就是最左节点
- 然后根据这个最左结点, 初始化head pre, 循环进入根节点开始连接
- 最后进入到右子树
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null) {
return null;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode head = null;
TreeNode pre = null;
//标识此时第一次遍历到最左
boolean isFirst = true;
while(pRootOfTree != null || !stack.isEmpty()) {
//连续放入左节点
while(pRootOfTree != null) {
stack.push(pRootOfTree);
pRootOfTree = pRootOfTree.left;
}
//取出最左元素 此时为表头
pRootOfTree = stack.pop();
if(isFirst) {
head = pRootOfTree;
pre = head;
isFirst = false;
} else {
//pre 当前节点的上一个节点,将当前节点和pre连接,并更新pre
pre.right = pRootOfTree;
pRootOfTree.left = pre;
pre = pRootOfTree;
}
pRootOfTree = pRootOfTree.right;
}
return head;
}9. 判断是不是二叉搜索树
题目链接 判断是不是二叉搜索树_牛客题霸_牛客网 (nowcoder.com)
题目要求
题目分析
(1) 栈+数组
- 创建栈用来遍历二叉树, 创建 ArrayList数组 用来保存中序遍历的结果(如果数组为递增的就是二叉搜索树)
- 下面就是给栈中遍历放元素结点,先放左节点,直到当前节点为null
- 出栈,此时这个出栈的元素最左节点,把这个节点的val 放入数组中
- 然后将右边结点也加入到栈中,同样进入右子树后,也是先访问最右结点
- 到最后所有结点遍历完后,就遍历数组,看数组是不是递增的
上代码
public boolean isValidBST (TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
ArrayList<Integer> arr = new ArrayList<>();
TreeNode head = root;
while(head != null || !stack.isEmpty()) {
while(head != null) {
stack.push(head);
head = head.left;
}
head = stack.pop();
//将当前结点加入到数组中
arr.add(head.val);
head = head.right;
}
//看这个数组是不是递增的
for(int i = 1; i < arr.size(); i++) {
if(arr.get(i-1) > arr.get(i)) {
return false;
}
}
return true;
}(2) 递归
- 创建一个pre 用来保存当前节点的上一个节点,初始化为最小值
- 下面开始递归左子树,看是不是BST
- 判断当前节点是不是小于前置节点，更新前置节点
- 最后由右子树的后面节点决定
Integer pre = Integer.MIN_VALUE;
public boolean isValidBST (TreeNode root) {
if(root == null) {
return true;
}
//先左递归,如果左树不为BST,就返回false
if(!isValidBST(root.left)) {
return false;
}
//当 pre(前一个值) > 当前节点值, 返回 false
if(pre > root.val) {
return false;
}
//如果满足前一个值小于当前值,就更新pre
pre = root.val;
return isValidBST(root.right);
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/91192.html
