1. 二叉树的锯齿形层序遍历
给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：给定二叉树 [3,9,20,null,null,15,7]
返回锯齿形层序遍历如下：
[
[3],
[20,9],
[15,7]
]
代码：
import java.util.*; class zigzagLevelOrder { public final static int NULL = Integer.MIN_VALUE; //用NULL来表示空节点 public static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public static 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; } } public static TreeNode createBinaryTree(Vector<Integer> vec) { if (vec == null || vec.size() == 0) { return null; } Queue<TreeNode> queue = new LinkedList<>(); TreeNode root = new TreeNode(vec.get(0)); queue.offer(root); int i = 1; while (!queue.isEmpty()) { int size = queue.size(); for (int j = 0; j < size; j++) { TreeNode node = queue.poll(); if (i < vec.size() && vec.get(i) != NULL) { node.left = new TreeNode(vec.get(i)); queue.offer(node.left); } i++; if (i < vec.size() && vec.get(i) != NULL) { node.right = new TreeNode(vec.get(i)); queue.offer(node.right); } i++; } } return root; } public static void main(String[] args) { Solution s = new Solution(); Integer[] nums = {3,9,20,NULL,NULL,15,7}; Vector<Integer> vec = new Vector<Integer>(Arrays.asList(nums)); TreeNode root = createBinaryTree(vec); System.out.println(s.zigzagLevelOrder(root)); } }
输出：
[[3], [20, 9], [15, 7]]
2. 从中序与后序遍历序列构造二叉树
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
代码：
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, 9, 20, 15, 7]
[9, 3, 15, 20, 7]
[9, 15, 7, 20, 3]
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
import java.util.*; class isBalanced { public final static int NULL = Integer.MIN_VALUE; //用NULL来表示空节点 public static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public static 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; } } public static TreeNode createBinaryTree(Vector<Integer> vec) { if (vec == null || vec.size() == 0) { return null; } Queue<TreeNode> queue = new LinkedList<>(); TreeNode root = new TreeNode(vec.get(0)); queue.offer(root); int i = 1; while (!queue.isEmpty()) { int size = queue.size(); for (int j = 0; j < size; j++) { TreeNode node = queue.poll(); if (i < vec.size() && vec.get(i) != NULL) { node.left = new TreeNode(vec.get(i)); queue.offer(node.left); } i++; if (i < vec.size() && vec.get(i) != NULL) { node.right = new TreeNode(vec.get(i)); queue.offer(node.right); } i++; } } return root; } public static void main(String[] args) { Solution s = new Solution(); Integer[] nums = {3,9,20,NULL,NULL,15,7}; Vector<Integer> vec = new Vector<Integer>(Arrays.asList(nums)); TreeNode root = createBinaryTree(vec); System.out.println(s.isBalanced(root)); Integer[] nums2 = {1,2,2,3,3,NULL,NULL,4,4}; vec = new Vector<Integer>(Arrays.asList(nums2)); root = createBinaryTree(vec); System.out.println(s.isBalanced(root)); Integer[] nums3 = {}; vec = new Vector<Integer>(Arrays.asList(nums3)); root = createBinaryTree(vec); System.out.println(s.isBalanced(root)); } }
输出：
true
false
true
