Java每日一练(20230410)

目录

1. 二叉树的锯齿形层序遍历  🌟🌟

2. 从中序与后序遍历序列构造二叉树  🌟🌟

3. 平衡二叉树  🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

---

1. 二叉树的锯齿形层序遍历

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：给定二叉树 [3,9,20,null,null,15,7]

       3

      /  \

    9  20

   /  \
15   7

返回锯齿形层序遍历如下：

[
[3],
[20,9],
[15,7]
]

代码：

public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}
}
class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> list = new LinkedList<>();if (root == null) {return list;}Stack<TreeNode> stack1 = new Stack<>();stack1.push(root);boolean postive = true;while (!stack1.isEmpty()) {Stack<TreeNode> stack2 = new Stack<>();List<Integer> subList = new LinkedList<>();while (!stack1.isEmpty()) {TreeNode current = stack1.pop();subList.add(current.val);if (postive) {if (current.left != null) {stack2.push(current.left);}if (current.right != null) {stack2.push(current.right);}} else {if (current.right != null) {stack2.push(current.right);}if (current.left != null) {stack2.push(current.left);}}}postive = !postive;stack1 = stack2;list.add(subList);}return list;}
}

---

2. 从中序与后序遍历序列构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

     3/ \9  20/  \
15   7

import java.util.*;
public class buildTreefrominpost {public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}}public static class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {return helper(inorder, postorder, postorder.length - 1, 0, inorder.length - 1);}public TreeNode helper(int[] inorder, int[] postorder, int postEnd, int inStart, int inEnd) {if (inStart > inEnd) {return null;}int currentVal = postorder[postEnd];TreeNode current = new TreeNode(currentVal);int inIndex = 0;for (int i = inStart; i <= inEnd; i++) {if (inorder[i] == currentVal) {inIndex = i;}}TreeNode left = helper(inorder, postorder, postEnd - (inEnd - inIndex) - 1, inStart, inIndex - 1);TreeNode right = helper(inorder, postorder, postEnd - 1, inIndex + 1, inEnd);current.left = left;current.right = right;return current;}}public static void main(String[] args) {Solution s = new Solution();System.out.println(s.buildTree(2));}
}

---

3. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

提示：

• 树中的节点数在范围 [0, 5000] 内
• -104 <= Node.val <= 104

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}
}
public class Solution {public boolean isBalanced(TreeNode root) {if (root == null) {return true;}return (Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1) && isBalanced(root.left)&& isBalanced(root.right);}public int maxDepth(TreeNode root) {if (root == null) {return 0;}return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;}
}

---

🌟 每日一练刷题专栏 🌟

✨ 持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！ 

🌟 收藏，你的青睐是我努力的方向！ 

✎ 评论，你的意见是我进步的财富！  

☸ 主页：https://hannyang.blog.csdn.net/ 

	Golang每日一练 专栏
	Python每日一练 专栏
	C/C++每日一练 专栏
	Java每日一练 专栏