public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> queue = new ArrayDeque<>();
if (root != null) {
queue.add(root);
}
while (!queue.isEmpty()) {
int n = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < n; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
res.add(level);
}
return res;
}
用List<List>> 先存储每一层，然后反转
94. 二叉树的中序遍历
145. 二叉树的后序遍历
剑指 Offer 33. 二叉搜索树的后序遍历序列
103. 二叉树的锯齿形层序遍历
105. 从前序与中序遍历序列构造二叉树
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || inorder == null) return null;
TreeNode root = buildTree(preorder, 0, preorder.length - 1, inorder, 0,
inorder.length - 1);
return root;
}
public TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) return null;
int rootVal = preorder[preStart];
TreeNode root = new TreeNode(rootVal);
int rootIndex = inStart;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
root.left = buildTree(preorder, preStart + 1, rootIndex + preStart - inStart, inorder, inStart, rootIndex - 1);
root.right = buildTree(preorder, rootIndex + preStart - inStart + 1, preEnd, inorder, rootIndex + 1, inEnd);
return root;
}
}
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder == null || postorder == null) return null;
return buildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
}
public TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
if (inStart > inEnd || postStart > postEnd) return null;
int rootVal = postorder[postEnd];
int index = postEnd;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
index = i;
break;
}
}
TreeNode root = new TreeNode(rootVal);
root.left = buildTree(inorder, inStart, index - 1, postorder, postStart, postStart + index - inStart - 1);
root.right = buildTree(inorder, index + 1, inEnd ,postorder, postStart + index - inStart, postEnd - 1);
return root;
}
}
class Solution {
private List<Integer> res = new ArrayList<>();
public List<Integer> rightSideView(TreeNode root) {
dfs(root, 0);
return res;
}
private void dfs(TreeNode root, int depth) {
if (root == null) {
return;
}
if (depth == res.size()) {
res.add(root.val);
}
++depth;
dfs(root.right, depth);
dfs(root.left, depth);
}
}
// 递归算法，迭代用广度搜索算法即可
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = root.left;
root.left = root.right;
root.right = left;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
return (A != null && B != null) && (isValid(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
}
private boolean isValid(TreeNode A, TreeNode B) {
if (B == null) return true;
if (A == null) return false;
return A.val == B.val && isValid(A.left, B.left) && isValid(A.right, B.right);
}
}
// 转化为求两棵树的镜像对称问题
class Solution {
public boolean isSymmetric(TreeNode root) {
return check(root, root);
}
private boolean check(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null) return false;
return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
}
}
class Solution {
public boolean isValidBST(TreeNode root) {
return isValid(root, Long.MAX_VALUE, Long.MIN_VALUE);
}
private boolean isValid(TreeNode p, long upper, long lower) {
if (p == null) return true;
if (p.val <= lower || p.val >= upper) return false;
return isValid(p.left, p.val, lower) && isValid(p.right, upper, p.val);
}
}
class Solution {
private int ans;
public int diameterOfBinaryTree(TreeNode root) {
depth(root);
return ans - 1;
}
private int depth(TreeNode p) {
if (p == null) {
return 0;
}
int left = depth(p.left);
int right = depth(p.right);
ans = Math.max(ans, left+right+1);
return Math.max(left, right) + 1;
}
}
341. 扁平化嵌套列表迭代器
剑指 Offer 37. 序列化二叉树
236. 二叉树的最近公共祖先
剑指 Offer 36. 二叉搜索树与双向链表
剑指 Offer 32 - I. 从上到下打印二叉树
剑指 Offer 34. 二叉树中和为某一值的路径
class Solution {
List<String> res = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
dfs(root, "");
return res;
}
private void dfs(TreeNode p, String cur) {
if (p.left == null && p.right == null) {
cur += p.val;
res.add(cur);
return;
}
if (p.left == null) {
cur += p.val + "->";
dfs(p.right, cur);
} else if (p.right == null) {
cur += p.val + "->";
dfs(p.left, cur);
} else {
cur += p.val + "->";
dfs(p.left, cur);
dfs(p.right, cur);
}
}
}
class Solution {
private int ans;
public int sumNumbers(TreeNode root) {
dfs(root, 0);
return ans;
}
private void dfs(TreeNode p, int curSum) {
curSum = curSum * 10 + p.val;
if (p.left == null && p.right == null) {
ans += curSum;
} else if (p.left == null) {
dfs(p.right, curSum);
} else if (p.right == null) {
dfs(p.left, curSum);
} else {
dfs(p.left, curSum);
dfs(p.right, curSum);
}
}
}
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null) return false;
return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) {
return root2;
}
if (root2 == null) {
return root1;
}
TreeNode root = new TreeNode(root1.val + root2.val);
root.left = mergeTrees(root1.left, root2.left);
root.right = mergeTrees(root1.right, root2.right);
return root;
}
}
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
if (root.left == null && root.right == null) return root.val == targetSum;
targetSum = targetSum - root.val;
if (root.left == null) {
return hasPathSum(root.right, targetSum);
}
if (root.right == null) {
return hasPathSum(root.left, targetSum);
}
return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
}
}
class Solution {
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if (root == null) return res;
dfs(root, new ArrayList<>(), targetSum);
return res;
}
private void dfs(TreeNode p, List<Integer> path, int targetSum) {
path.add(p.val);
if (p.left == null && p.right == null) {
if (p.val == targetSum)
res.add(new ArrayList<>(path));
return;
}
targetSum = targetSum - p.val;
if (p.left == null) {
dfs(p.right, path, targetSum);
return;
}
if (p.right == null) {
dfs(p.left, path, targetSum);
return;
}
dfs(p.left, new ArrayList<>(path), targetSum);
dfs(p.right, new ArrayList<>(path), targetSum);
}
}
剑指 Offer 32 - II. 从上到下打印二叉树 II
剑指 Offer 32 - III. 从上到下打印二叉树 III
110. 平衡二叉树
剑指 Offer 68 - II. 二叉树的最近公共祖先
662. 二叉树最大宽度
872. 叶子相似的树
109. 有序链表转换二叉搜索树
95. 不同的二叉搜索树 II
297. 二叉树的序列化与反序列化
剑指 Offer 55 - II. 平衡二叉树
108. 将有序数组转换为二叉搜索树
面试题 04.02. 最小高度树
173. 二叉搜索树迭代器
124. 二叉树中的最大路径和
