每一步向前都是向自己的梦想更近一步,坚持不懈,勇往直前!
第一题: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;}
}