【树】 （1）Leetcode 12道二叉树基础题
2020-05-31 本文已影响0人
AlexLJS
94. 二叉树的中序遍历
札记： 说一下非递归遍历
前中后序遍历指的是 head节点的是“最先遍历”，还是“中间”，还是“最后”。通过对树的分解，可以发现树可以以head和left组成的左边界拆分，right也可以作为其子树的head ， 进行同样拆分。所以要中序的顺序 ，只需处理left和head即可。我们先准备一个stack，左边界依次压栈，pop出栈right压栈重复这个过程。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
notRe(res, root);
return res;
}
public static void inorder(List<Integer> res, TreeNode root){
if (root == null) return;
if (root.left != null) inorder(res, root.left);
res.add(root.val);
if (root.right != null) inorder(res, root.right);
}
public static void notRe(List<Integer> res, TreeNode root){
if (root == null) return;
TreeNode temp = root;
Stack<TreeNode> stack = new Stack<>();
while(!stack.isEmpty() || temp != null){
if (temp != null){
stack.push(temp);
temp = temp.left;
}else{
temp = stack.pop();
res.add(temp.val);
temp = temp.right;
}
}
}
}
其他 ： 线索二叉树 和 莫里斯遍历
102. 二叉树的层序遍历
题解： 有别于普通层序遍历， 题目要求分层输出。 基本思路使用队列， 但是在每层结束的时候，队列中加入dummy，表示本层结束。 当遇到dummy的时， 本层node已全部出队列，下层node全部进入队列。list写入result即可。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
TreeNode dummy = new TreeNode(Integer.MIN_VALUE);
queue.add(root);
queue.add(dummy);
List<List<Integer>> res = new ArrayList<>();
List<Integer> list = new ArrayList<>();
if(root == null) return res;
while(!queue.isEmpty() ){
TreeNode ele = queue.poll();
if (ele != dummy){
list.add(ele.val);
if(ele.left != null) queue.add(ele.left);
if(ele.right != null) queue.add(ele.right);
}else{
res.add(list);
if(queue.isEmpty()) break;//the last floor
queue.add(dummy);
list = new ArrayList<>();
}
}
return res;
}
}
103. 二叉树的锯齿形层次遍历
题解： 与上题同理，额外添加flag标记，表示本层输出的list是否需要反转。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
TreeNode dummy = new TreeNode(-Integer.MAX_VALUE);
List<List<Integer>> res = new ArrayList<>();
List<Integer> tempList = new ArrayList<>();
boolean flag = false;
if(root==null) return res;
queue.add(root);
queue.add(dummy);
while(!queue.isEmpty()){
TreeNode temp = queue.poll();
if(temp != dummy){
tempList.add(temp.val);
if(temp.left != null) queue.add(temp.left);
if(temp.right != null) queue.add(temp.right);
}else{//dummy
if(flag) Collections.reverse(tempList);
res.add(tempList);
if(queue.isEmpty()) break;
queue.add(dummy);
flag = !flag;
tempList = new ArrayList<>();
}
}
return res;
}
}
105. 从前序与中序遍历序列构造二叉树
题解：
构造二叉树的问题最适合递归，连接“左中右”三个节点，递归到所有节点即可构建整棵树。
本题，中序遍历的结果用于确定先序遍历的数的结构。
对于任意一棵树而言，前序遍历的形式总是
[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是
[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
static Map<Integer,Integer> inorderMap = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
int len = preorder.length;
for(int i = 0; i < inorder.length; i++){
inorderMap.put(inorder[i],i);
}
return process(preorder,inorder,0,len-1,0,len-1);
}
public static TreeNode process(int[] preorder, int[] inorder, int pl, int pr, int il, int ir){
if (pl > pr) {
return null;
}
TreeNode root = new TreeNode(preorder[pl]);
int inorderRoot = inorderMap.get(preorder[pl]);
root.left = process(preorder,inorder,pl+1,inorderRoot+pl-il,il,inorderRoot-1);
root.right = process(preorder,inorder,inorderRoot+pl-il+1,pr,inorderRoot+1,ir);
return root;
}
}
106. 从中序与后序遍历序列构造二叉树
题解： 类比上一题解决方法
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
static Map<Integer,Integer> inorderMap = new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
int len = inorder.length;
for(int i = 0; i < inorder.length; i++){
inorderMap.put(inorder[i],i);
}
return proccess(inorder,postorder,0,len-1,0,len-1);
}
public static TreeNode proccess(int[] inorder, int[] postorder, int il, int ir, int pl, int pr){
if(pl > pr || il > ir) return null;
// int inorderRoot = -1;
// for(int i = 0; i < inorder.length; i++ ){
// if(postorder[pr] == inorder[i]){
// inorderRoot = i;
// break;
// }
// }
TreeNode root = new TreeNode(postorder[pr]);
int inorderRoot = inorderMap.get(postorder[pr]);
root.left = proccess(inorder, postorder, il, inorderRoot-1, pl, inorderRoot-1-il+pl);
root.right = proccess(inorder, postorder, inorderRoot+1, ir, pl-il+inorderRoot, pr-1);
return root;
}
}
107. 二叉树的层次遍历 II
题解： 这道题还是二叉树的层序遍历 ， 这次将最后的结果集合进行反转即可。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
TreeNode temp = root;
TreeNode dummy = new TreeNode(-Integer.MAX_VALUE);
Queue<TreeNode> queue = new LinkedList<>();
List<Integer> listTemp = new ArrayList<>();
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
queue.add(temp);
queue.add(dummy);
while(!queue.isEmpty()){
TreeNode ele = queue.poll();
if(ele != dummy){
listTemp.add(ele.val);
if(ele.left != null){
queue.add(ele.left);
}
if(ele.right != null){
queue.add(ele.right);
}
}else{
res.add(listTemp);
listTemp = new ArrayList<>();
if(queue.isEmpty()) break;
queue.add(dummy);
}
}
List<List<Integer>> reres = new ArrayList<>();
for(int i = res.size()-1; i >= 0; i--){
reres.add(res.get(i));
}
return reres;
}
}
108. 将有序数组转换为二叉搜索树
题解：这是个有序数组， 把中点作为根节点，递归下去， 自动转为平衡搜索二叉树。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if (nums.length == 0) return null;
return process(nums, 0, nums.length-1);
}
public static TreeNode process(int[] nums, int l, int r){
if (l == r) return new TreeNode(nums[l]);
if (r == l+1) {
TreeNode left = new TreeNode(nums[l]);
TreeNode right = new TreeNode(nums[r]);
right.left = left;
return right;
}
int mid = l + (r-l)/2;
TreeNode root = new TreeNode(nums[mid]);
root.left = process(nums,l,mid-1);
root.right = process(nums,mid+1,r);
return root;
}
}
109. 有序链表转换二叉搜索树
题解 ：可以将链表转成数组，空间换时间， 这样就回到上一题的解。 也可以直接双指针处理链表，寻找中点。 评论区抄了如下代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if(head == null) return null;
else if(head.next == null) return new TreeNode(head.val);
ListNode pre = head;
ListNode p = pre.next;
ListNode q = p.next;
//找到链表的中点p
while(q!=null && q.next!=null){
pre = pre.next;
p = pre.next;
q = q.next.next;
}
//将中点左边的链表分开
pre.next = null;
TreeNode root = new TreeNode(p.val);
root.left = sortedListToBST(head);
root.right = sortedListToBST(p.next);
return root;
}
}
110. 平衡二叉树
题解： 判断平衡性，基本功。
平衡条件：
左子树平衡
右子树平衡
左右子树高度差＜＝１
如何记录高度差？ 采用自底而上的方式， 递归最深层高度是0， 逐次左子树与右子树最大高度+1。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
return process(root).isBalanced;
}
public static Info process(TreeNode head){
if (head == null) return new Info(true,0);
Info leftTree = process(head.left);
if (!leftTree.isBalanced) return leftTree;
Info rightTree = process(head.right);
if(!rightTree.isBalanced) return rightTree;
if (Math.abs(leftTree.level - rightTree.level)>1) return new Info(false,-1);
return new Info(true,Math.max(leftTree.level,rightTree.level)+1);
}
public static class Info{
boolean isBalanced;
int level;
public Info(boolean isBalanced, int level){
this.isBalanced = isBalanced;
this.level = level;
}
}
}
111. 二叉树的最小深度
题解： 递归，深度优先遍历。 抽象成： 左子树最小深度 + 右子树最小深度 +1 （head节点）。
当然也可以用前几个题的套路 ， 层序遍历。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0; // 特殊输入
if ((root.left == null) && (root.right == null)) {
return 1;
}//head
int minDepth = Integer.MAX_VALUE;
//单边树为null ，不能进入递归
if (root.left != null){
minDepth = Math.min( minDepth(root.left) , minDepth);
}
if (root.right != null){
minDepth = Math.min( minDepth(root.right) , minDepth);
}
return minDepth+1;
}
}
// 层序遍历参考
public int minDepth(TreeNode root) {
if (root == null) return 0;
int depth = 1;
TreeNode temp = root;
TreeNode dummy = new TreeNode(-Integer.MAX_VALUE);
Queue<TreeNode> queue = new LinkedList<>();
queue.add(temp);
queue.add(dummy);
while(!queue.isEmpty()){
TreeNode ele = queue.poll();
if(ele != dummy){
if(ele.left != null) queue.add(ele.left);
if(ele.right != null) queue.add(ele.right);
if(ele.left == null && ele.right == null) break;
}else{
depth++;
if(queue.isEmpty())break;
queue.add(dummy);
}
}
return depth;
}
注意： 递归子问题化，在二叉树中是一种结构的拆分， 或是分解成子树（左右两部分），或是拆分成单边。
112. 路径总和
题解： 这题直接抄答案，答案写的太精彩了，主要看下一道进阶版路径和。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null)return false;
sum -= root.val;
if ((root.left == null) && (root.right == null))return (sum == 0);
return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
}
}
113. 路径总和 II
题解 ： 很多空间浪费 和重复计算的算法。 mark 一下， 下篇用回溯改进一下。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> res = new ArrayList<>();
process(root, sum, new ArrayList<>(), res);
return res;
}
public static void process(TreeNode root, int sum, ArrayList<Integer> list, List<List<Integer>> res){
if (root == null) return;
ArrayList<Integer> tempList = new ArrayList<Integer>();
for(int i = 0; i < list.size(); i++){
tempList.add(list.get(i));
}
tempList.add(root.val);
sum -= root.val;
if ((root.left == null) && (root.right == null) && (sum == 0)){
res.add(tempList);
return;
}
process(root.left, sum, tempList,res);
process(root.right, sum, tempList,res);
}
}
本次留坑 ：
1、 95、96 看不懂
95. 不同的二叉搜索树 II
2、113 需要回溯改进
（下期深入研究一下二叉树）
