106. 从中序与后序遍历序列构造二叉树
// 树 前序/后序 和 中序 长度应该是一致的
// 前序 和 中序 构造 从前序中取值构造
// 后序 和 中序 构造 从后序中取值构造
class Solution {
int[] post;
HashMap<Integer, Integer> mem = new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
post = postorder;
for (int i = 0; i < inorder.length; i++) {
mem.put(inorder[i], i);
}
return buildTree(0, inorder.length - 1, 0, postorder.length - 1);
}
public TreeNode buildTree(int inL, int inR, int poL, int poR) {
if (poL > poR) {
return null;
}
int mid = mem.get(post[poR]);
TreeNode root = new TreeNode(post[poR]);
root.left = buildTree(inL, mid - 1, poL, poL + mid - 1 - inL);
root.right = buildTree(mid + 1, inR, poL + mid - inL, poR - 1);
return root;
}
}
105. 从前序与中序遍历序列构造二叉树
// 关键就是 前后序取值构造，中序辅助位置
class Solution {
int[] pre;
HashMap<Integer, Integer> mem = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
pre = preorder;
for (int i = 0; i < inorder.length; i++) {
mem.put(inorder[i], i);
}
return buildTree(0, preorder.length - 1, 0, inorder.length - 1);
}
public TreeNode buildTree(int pl, int pr, int il, int ir) {
if (pl > pr) {
return null;
}
int mid = mem.get(pre[pl]);
TreeNode root = new TreeNode(pre[pl]);
root.left = buildTree(pl + 1, pl + mid - il, il, mid - 1);
root.right = buildTree(pl + mid - il + 1, pr, mid + 1, ir);
return root;
}
}
103. 二叉树的锯齿形层次遍历
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if (root == null)
return new ArrayList();
List<List<Integer>> result = new ArrayList<>();
int flag = 0;
Deque<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> path = new ArrayList();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null)
queue.add(node.left);
if (node.right != null)
queue.add(node.right);
path.add(node.val);
}
if (flag % 2 == 1) {
Collections.reverse(path);
}
flag++;
if (path.size() != 0) {
result.add(path);
}
}
return result;
}
104.二叉树的最大深度
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
110. 平衡二叉树
class Solution {
private boolean result = true;
public boolean isBalanced(TreeNode root) {
maxHeight(root);
return result;
}
private int maxHeight(TreeNode root) {
if (root == null) return 0;
int lHeight = maxHeight(root.left);
int rHeight = maxHeight(root.right);
if (Math.abs(lHeight - rHeight) > 1) {
result = false;
return -1;
}
return Math.max(lHeight, rHeight) + 1;
}
}
543. 二叉树的直径
class Solution {
int length = 0;
public int diameterOfBinaryTree(TreeNode root) {
dfsLength(root);
return length;
}
private int dfsLength(TreeNode root) {
if (root == null) {
return 0;
}
int lHeight = dfsLength(root.left);
int rHeight = dfsLength(root.right);
length = Math.max(length, lHeight + rHeight);
return Math.max(lHeight, rHeight) + 1;
}
}
226. 翻转二叉树
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null)
return null;
TreeNode temp = root.left;
root.left = invertTree(root.right);
root.right = invertTree(temp);
return root;
}
}
617. 合并二叉树
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null)
return t2;
if (t2 == null)
return t1;
t1.val = t1.val + t2.val;
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
}
}
112. 路径总和
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null)
return false;
if (root.left == null && root.right == null && sum == root.val) {
return true;
}
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
}
437. 路径总和 III
class Solution {
int pathCount = 0;
public int pathSum(TreeNode root, int sum) {
if (root == null)
return pathCount;
sumChild(root, sum);
pathSum(root.left, sum);
pathSum(root.right, sum);
return pathCount;
}
public void sumChild(TreeNode root, int sum) {
if (root == null)
return;
if (root.val == sum)
pathCount++;
sumChild(root.left, sum - root.val);
sumChild(root.right, sum - root.val);
}
}
572. 另一个树的子树
class Solution {
boolean result = true;
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null && t == null)
return true;
if (s == null || t == null) {
return false;
}
return subTreeSame(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
}
public boolean subTreeSame(TreeNode s, TreeNode t) {
if (s == null && t == null)
return true;
if (s == null || t == null)
return false;
return s.val == t.val && subTreeSame(s.left, t.left) && subTreeSame(s.right, t.right);
}
}
101. 对称二叉树
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null)
return true;
if (root.left == null && root.right == null)
return true;
if (root.left != null && root.right != null) {
return jude(root.left, root.right);
} else {
return false;
}
}
public static boolean jude(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null || right == null) {
return false;
}
if (left.val == right.val) {
return jude(left.right, right.left) && jude(left.left, right.right);
} else {
return false;
}
}
}
199. 二叉树的右视图
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList();
if (root == null) {
return result;
}
Deque<TreeNode> queue = new LinkedList();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
result.add(queue.peekLast().val);
while (size > 0) {
TreeNode cur = queue.poll();
if (cur.left != null) {
queue.add(cur.left);
}
if (cur.right != null) {
queue.add(cur.right);
}
size--;
}
}
return result;
}
113. 路径总和 II
Stack<Integer> path = new Stack();
List<List<Integer>> result = new ArrayList();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if (root == null) {
return result;
}
dfs(root, sum);
return result;
}
public void dfs(TreeNode root, int sum) {
if (root == null) {
return;
}
path.push(root.val);
if (root.left == null && root.right == null && sum == root.val) {
result.add(new ArrayList(path));
}
dfs(root.left, sum - root.val);
dfs(root.right, sum - root.val);
path.pop();
}
124. 二叉树中的最大路径和
int path = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if (root == null)
return path;
dfsSum(root);
return path;
}
public int dfsSum(TreeNode root) {
if (root == null)
return 0;
int left = Math.max(dfsSum(root.left), 0);
int right = Math.max(dfsSum(root.right), 0);
path = Math.max(path, left + right + root.val);
return Math.max(left, right) + root.val;
}
