每一步向前都是向自己的梦想更近一步，坚持不懈，勇往直前！
第一题：101. 对称二叉树 - 力扣（LeetCode）
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null){
return true;
}
Stack<TreeNode> st = new Stack();
st.push(root.left);
st.push(root.right);
while(!st.isEmpty()){
TreeNode nodeA = st.pop();
TreeNode nodeB = st.pop();
if(nodeA == null && nodeB == null){
continue;
}
if((nodeA == null && nodeB != null) || (nodeA != null && nodeB == null) || nodeA.val != nodeB.val){
return false;
}
st.push(nodeA.left);
st.push(nodeB.right);
st.push(nodeA.right);
st.push(nodeB.left);
}
return true;
}
}
显然，我们使用栈来递归的速度是很慢的，只要是树，我们就用递归好了，天然有优势（对于每一个节点，面临的问题相同，符合复杂问题分为子问题这一原则）。
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode left, TreeNode right) {
// 如果两个节点都为空，视为对称
if (left == null && right == null) {
return true;
}
// 如果有一个节点为空，或者节点值不相等，不对称
if (left == null || right == null || left.val != right.val) {
return false;
}
// 递归判断左子树的左子节点和右子树的右子节点，以及左子树的右子节点和右子树的左子节点
return isMirror(left.left, right.right) && isMirror(left.right, right.left);
}
}
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode left, TreeNode right) {
// 如果两个节点都为空，视为对称
if (left == null && right == null) {
return true;
}
// 如果有一个节点为空，或者节点值不相等，不对称
if (left == null || right == null || left.val != right.val) {
return false;
}
// 递归判断左子树的左子节点和右子树的右子节点，以及左子树的右子节点和右子树的左子节点
return isMirror(left.left, right.right) && isMirror(left.right, right.left);
}
}
第二题：102. 二叉树的层序遍历 - 力扣（LeetCode）
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null){
return new ArrayList<>();
}
List<List<Integer>> res = new ArrayList<>();
Deque<TreeNode> deque = new ArrayDeque<>();
deque.offerLast(root);
while(!deque.isEmpty()){
//主要每一层都用一个list，结束之后把这个list add到res中
int len = deque.size();
List<Integer> path = new ArrayList<>();
while(len-- > 0){
TreeNode node = deque.pollFirst();
path.add(node.val);
if(node.left != null){
deque.offerLast(node.left);
}
if(node.right != null){
deque.offerLast(node.right);
}
}
res.add(path);
}
return res;
}
}第三题：103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）
import java.util.*;
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if(root == null){
return new ArrayList<>();
}
List<List<Integer>> res = new ArrayList<>();
Deque<TreeNode> deque = new ArrayDeque<>();
deque.offerLast(root);
//多一个判断而已，本质与102题没有区别
int flag = 1;
while(!deque.isEmpty()){
int len = deque.size();
List<Integer> path = new ArrayList<>();
for(int i = 0; i < len; i++){
TreeNode node;
if(flag == 1){
node = deque.pollFirst();
if(node.left != null){
deque.offerLast(node.left);
}
if(node.right != null){
deque.offerLast(node.right);
}
} else {
node = deque.pollLast();
if(node.right != null){
deque.offerFirst(node.right);
}
if(node.left != null){
deque.offerFirst(node.left);
}
}
path.add(node.val);
}
res.add(path);
flag = -flag; // 改变方向
}
return res;
}
}
第四题：104. 二叉树的最大深度 - 力扣（LeetCode）
class Solution {
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
//挑选最高的一个分支加上来
return Math.max(left, right) + 1;
}
}第五题：105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
//因为前序的第一个一定是根节点
//中序可以找到根节点，该节点左边一定属于左子树，右边一定属于右子树
//所以我们通过一个map记录下位置，可以采用迭代的方式来一个个确定位置
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < inorder.length; i++){
map.put(inorder[i], i);
}
TreeNode head = helper(0, preorder.length - 1, map, preorder, 0);
return head;
}
private static TreeNode helper(int low, int high, Map<Integer, Integer> map, int[] preorder, int idx){
if(low > high){
return null;
}
int val = preorder[idx];
int index = map.get(val);
TreeNode head = new TreeNode(val);
head.left = helper(low, index - 1, map, preorder, idx + 1);
head.right = helper(index + 1, high, map, preorder, idx + (index - low) + 1);
return head;
}
}
