二叉树
二叉树--二叉树的递归遍历
题目:
-
题解:
前序遍历
class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<Integer>(); 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); } }
中序遍历
class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); inorder(root, res); return res; } void inorder(TreeNode root, List<Integer> list) { if (root == null) { return; } inorder(root.left, list); list.add(root.val); // 注意这一句 inorder(root.right, list); } }
后续遍历
class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); postorder(root, res); return res; } void postorder(TreeNode root, List<Integer> list) { if (root == null) { return; } postorder(root.left, list); postorder(root.right, list); list.add(root.val); // 注意这一句 } }
解析:递归遍历,前序遍历:根左右遍历。中序遍历:左根右。后续遍历:左右根。
二叉树--二叉树的迭代遍历
题目:
题解:
前序遍历
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result= new ArrayList<>();
if(root==null){
return result;
}
Stack<TreeNode> stack =new Stack();
stack.push(root);
while(!stack.isEmpty()){
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;
}
}
中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
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;
}
}
后序遍历:
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
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;
}
}
解析:
前序遍历:
前序遍历如图所示:
中序遍历如图所示:
后续遍历类似。
二叉树--二叉树的层序遍历
题目:力扣题目链接
给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]
示例 2:
输入:root = [1]
输出:[[1]]
示例 3:
输入: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>> resList= new ArrayList<List<Integer>>();
public List<List<Integer>> levelOrder(TreeNode root) {
check(root);
return resList;
}
public void check(TreeNode node){
if(node ==null){
return;
}
Queue<TreeNode> que= new LinkedList<TreeNode>();
que.offer(node);
while(!que.isEmpty()){
List<Integer> itemList= new ArrayList<Integer>();
int len=que.size();
while(len>0){
TreeNode tmpNode = que.poll();
itemList.add(tmpNode.val);
if(tmpNode.left!=null){
que.offer(tmpNode.left);
}
if(tmpNode.right!=null){
que.offer(tmpNode.right);
}
len--;
}
resList.add(itemList);
}
}
}
解析:
借助队列:
用一个list集合嵌套一个list集合里面包含每一层的数值,借助队列,把根元素加到队列里面,统计队列里面元素个数,弹出一个元素,加到tmplist集合里面,再把弹出元素的左右节点(如果有)加入队列,len--,直到把原始队列里面元素全部弹完,len=0.然后把这一层的元素加到resList队列里面,不断遍历循环,直到队列为空结束,最后返回reslist,实现二叉树的层序遍历。
二叉树--翻转二叉树
题目:
翻转一棵二叉树。
题解:
迭代法:
/**
* 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 TreeNode invertTree(TreeNode root) {
if(root==null){
return null;
}
ArrayDeque<TreeNode> deque= new ArrayDeque<>();
deque.offer(root);
while(!deque.isEmpty()){
int size=deque.size();
while(size-->0){
TreeNode node= deque.poll();
swap(node);
if(node.left!=null){
deque.offer(node.left);
}
if(node.right!=null){
deque.offer(node.right);
}
}
}
return root;
}
public void swap(TreeNode root){
TreeNode t=root.left;
root.left=root.right;
root.right=t;
}
}
解析:
ArrayDeque的介绍:
ArrayDeque是 Deque接口的一个实现,使用了可变数组,所以没有容量上的限制。同时, ArrayDeque是线程不安全的,在没有外部同步的情况下,不能再多线程环境下使用。
ArrayDeque是 Deque的实现类,可以作为栈来使用,效率高于 Stack;也可以作为队列来使用,效率高于 LinkedList。
ArrayDeque 是 Java 集合中双端队列的数组实现,双端队列的链表实现(LinkedList)
需要注意的是, ArrayDeque不支持 null值。
用ArrayDeque当作一个队列,先把根节点放入队列中,当队列不为空,且队列中元素大于0时,先弹出一个元素,把这个元素的左右子树进行交换,当存在左子树或右子树的情况,则依次加入队列中
递归法:
/**
* 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 TreeNode invertTree(TreeNode root) {
if(root==null){
return null;
}
invertTree(root.left);
invertTree(root.right);
swapChildren(root);
return root;
}
private void swapChildren(TreeNode root) {
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
}
}
解析:当根节点不存在时返回null,存在则把根的左子树放入递归操作,然后在把右子树放入递归操作,接着执行交换的方法。递归完成后,也完成了反转的逻辑。
二叉树--对称二叉树
题目:力扣题目链接
给定一个二叉树,检查它是否是镜像对称的。
题解:
递归法:
/**
* 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 boolean isSymmetric(TreeNode root) {
return compare(root.left,root.right);
}
private boolean compare(TreeNode left,TreeNode right){
if(left==null&&right!=null){
return false;
}
if(left!=null&&right==null){
return false;
}
if(left==null&&right==null){
return true;
}
if(left.val!=right.val){
return false;
}
//比较外侧
boolean compareOutside= compare(left.left,right.right);
//比较内测
boolean compareInside= compare(left.right,right.left);
return compareOutside&&compareInside;
}
}
解析:把不对称或对称的情况进行判断返回,分别递归比较外侧和内测,最后返回内外侧即可。
迭代法:使用双端队列,相当于两个栈
/**
* 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 boolean isSymmetric(TreeNode root) {
Deque<TreeNode> deque = new LinkedList<>();
deque.offerFirst(root.left);
deque.addLast(root.right);
while(!deque.isEmpty()){
TreeNode leftNode= deque.pollFirst();
TreeNode rightNode=deque.pollLast();
if(leftNode==null&&rightNode==null){
continue;
}
if(leftNode==null||rightNode==null||leftNode.val!=rightNode.val){
return false;
}
deque.offerFirst(leftNode.left);
deque.offerFirst(leftNode.right);
deque.offerLast(rightNode.right);
deque.offerLast(rightNode.left);
}
return true;
}
}
解析:双端队列往头插入根节点的左节点,往尾插入根节点的右节点,在栈不为空的情况下,分别从两端弹出,然后判断对称条件进行返回,最后往栈里头部插入左节点的左节点,再往头部插入左节点的右节点,继续往尾部插入右节点的右节点,最后往尾部插入右节点的左节点,使弹出的两个元素全为外侧或全为内侧进行检查是否为轴对称。,当栈为空时,表示二叉树中所有元素进行了轴对称检查。
迭代法:使用普通队列:
public boolean isSymmetric3(TreeNode root) {
Queue<TreeNode> deque = new LinkedList<>();
deque.offer(root.left);
deque.offer(root.right);
while (!deque.isEmpty()) {
TreeNode leftNode = deque.poll();
TreeNode rightNode = deque.poll();
if (leftNode == null && rightNode == null) {
continue;
}
// if (leftNode == null && rightNode != null) {
// return false;
// }
// if (leftNode != null && rightNode == null) {
// return false;
// }
// if (leftNode.val != rightNode.val) {
// return false;
// }
// 以上三个判断条件合并
if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
return false;
}
// 这里顺序与使用Deque不同
deque.offer(leftNode.left);
deque.offer(rightNode.right);
deque.offer(leftNode.right);
deque.offer(rightNode.left);
}
return true;
}
解析:同上面
二叉树--二叉树的最大深度
题目:力扣题目链接
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回它的最大深度 3 。
题解:递归法:
class Solution {
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
int leftDepth= maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth,rightDepth)+1;
}
}
解析:如果根节点为空最大深度为0,根节点不为空时,分别递归左子树和右子树,最后选择深度较大者加上根节点则为二叉树的最大深度。
题解:迭代法:
/**
* 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) {
if(root==null){
return 0;
}
Deque<TreeNode> deque= new LinkedList();
deque.offer(root);
int depth=0;
while(!deque.isEmpty()){
int size=deque.size();
depth++;
for(int i=0;i<size;i++){
TreeNode node=deque.poll();
if(node.left!=null){
deque.offer(node.left);
}
if(node.right!=null){
deque.offer(node.right);
}
}
}
return depth;
}
}
解析:无根节点时,深度为0。有根节点,用双端队列解决此题,先把根节点放入队列中,当队列不为空时,深度加一
遍历出队列的大小,遍历size次,当左节点不为空时,队列中加入左节点,右节点不为空时,队列加入右节点。不断循环遍历直到队列为空,返回深度。
二叉树--N叉树的最大深度
给定一个 n 叉树,找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
例如,给定一个 3叉树 :
我们应返回其最大深度,3
题解:递归法:
/*
// 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 int maxDepth(Node root) {
if(root==null){
return 0;
}
int depth=0;
if(root.children != null){
for(Node child:root.children){
depth=Math.max(depth,maxDepth(child));
}
}
return depth+1;
}
}
解析:根节点为空返回0,不为空,当根的子节点不为空时,遍历出每个节点,把这个节点进行递归,比较出最大深度。
迭代法:
/*
// 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 int maxDepth(Node root) {
if(root==null){
return 0;
}
int depth=0;
Queue<Node> que= new LinkedList<>();
que.add(root);
while(!que.isEmpty()){
depth++;
int len=que.size();
while(len>0){
Node node= que.poll();
for (int i = 0; i < node.children.size(); i++)
if (node.children.get(i) != null)
que.offer(node.children.get(i));
len--;
}
}
return depth;
}
}
二叉树--二叉树的最小深度
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
返回它的最小深度 2
题解:递归法:
/**
* 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) {
if(root==null){
return 0;
}
int leftDepth= minDepth(root.left);
int rightDepth=minDepth(root.right);
if(root.left==null){
return rightDepth+1;
}
if(root.right==null){
return leftDepth+1;
}
return Math.min(leftDepth, rightDepth) + 1;
}
}
解析:递归遍历根节点的左节点和右节点,如果根的左节点为空,则深度为右节点的深度加1,如果根的右节点为空,则深度为左节点深度加1
题解:迭代法:
/**
* 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) {
if(root==null){
return 0;
}
Deque<TreeNode> deque= new LinkedList<>();
deque.offer(root);
int depth=0;
while(!deque.isEmpty()){
int size= deque.size();
depth++;
for(int i=0;i<size;i++){
TreeNode poll=deque.poll();
if(poll.left==null&&poll.right==null){
return depth ;
}
if(poll.left!=null){
deque.offer(poll.left);
}
if(poll.right!=null){
deque.offer(poll.right);
}
}
}
return depth;
}
}
题解:使用队列解题,先把根节点放入队列中,声明出深度,当队列不为空时,深度加1,遍历放入队列中的元素,弹出一个元素,如果发现是叶子节点,则返回该深度,如果发现弹出节点poll的左节点不为空,则加入队列里面,右节点不为空则加到队列里面,直到遍历完成,返回对应的最小深度。
二叉树--完全二叉树的节点个数
给出一个完全二叉树,求出该树的节点个数。
示例 1:
- 输入:root = [1,2,3,4,5,6]
- 输出:6
示例 2:
- 输入:root = []
- 输出:0
示例 3:
- 输入:root = [1]
- 输出:1
提示:
-
树中节点的数目范围是[0, 5 * 10^4]
-
0 <= Node.val <= 5 * 10^4
-
题目数据保证输入的树是 完全二叉树
题解:递归法
/**
* 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 countNodes(TreeNode root) {
if(root==null){
return 0;
}
return countNodes(root.left)+countNodes(root.right)+1;
}
}
解析:递归根的左节点和根的右节点得出最后的节点个数再加1即可
题解:迭代法
/**
* 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 countNodes(TreeNode root) {
if(root==null){
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int result=0;
while(!queue.isEmpty()){
int size = queue.size();
while(size-->0){
TreeNode node= queue.poll();
result++;
if(node.left!=null){
queue.offer(node.left);
}
if(node.right!=null){
queue.offer(node.right);
}
}
}
return result;
}
}
解析:利用迭代法,使用一个队列,队列中先加入根节点,定义总数变量,当队列不为空时,,先拿到队列的个数,当队列个数大于1时,先让size-1,弹出一个元素,节点个数加1,当弹出的节点的左节点不为空时,则加入队列中,当弹出节点右节点不为空时,则加入到队列中,不断的去迭代,最后统计出最后的个数。
二叉树--平衡二叉树
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
/**
* 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 boolean isBalanced(TreeNode root) {
return getHeight(root)!=-1;
}
private int getHeight(TreeNode root){
if(root==null){
return 0;
}
int LeftHeight=getHeight(root.left);
if(LeftHeight==-1){
return -1;
}
int RightHeight = getHeight(root.right);
if(RightHeight==-1){
return -1;
}
if(Math.abs(LeftHeight-RightHeight)>1){
return -1;
}
return Math.max(LeftHeight,RightHeight) + 1;
}
}
解析:首先设计当获取二叉树的高度不是-1时,则返回正确,否则不满足要求。编写函数,首先如果根节点也没有,直接返回0,且满足要求。然后再把根的递归查左节点的高度,如果高度为-1,则不满足平衡二叉树,直接返回-1,根的右节点也是这样。接着如果左节点的高度和右节点的高度相差超过了1,则不是高度平衡的二叉树返回-1。否则是一个高度平衡二叉树,返回对应的高度。
二叉树--二叉树的所有路径
题目:
给定一个二叉树,返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
题解:递归法
/**
* 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<String> binaryTreePaths(TreeNode root) {
List<String> res= new ArrayList<>();//最终要存的
if(root==null){
return res;
}
List<Integer> paths= new ArrayList<>();//结果路径
traversal(root,res,paths);
return res;
}
public void traversal(TreeNode root,List<String> res,List<Integer> paths){
paths.add(root.val);
if(root.left==null&&root.right==null){
StringBuilder sb= new StringBuilder();
for(int i=0;i<paths.size()-1;i++){
sb.append(paths.get(i)).append("->");
}
sb.append(paths.get(paths.size()-1));
res.add(sb.toString());
return;
}
if (root.left != null) {
traversal(root.left, res,paths);
paths.remove(paths.size() - 1);// 回溯
}
if (root.right != null) {
traversal(root.right, res,paths);
paths.remove(paths.size() - 1);// 回溯
}
}
}
解析:定义一个最终存的list和结果路径的list,先把根的值放入结果路径的list,当根的左节点和右节点都为空时,定义一个StringBuilder开始追加内容,把一个路径上的前size-1个节点放入paths里面并且每个节点加上->,最后额外加上最后一个节点,把这一整个路径放入最终集合res里面,返回即可,如果root的左节点或者右节点不为空时,则开始递归,并且回溯,递归一个回溯一个。最终完成了返回从根节点到叶子节点的路径。
原文链接:https://www.cnblogs.com/zixiangm/p/17260297.html
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:代码随想录–二叉树 - Python技术站