二叉树的递归遍历
前序遍历
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
res.add(root.val);
if (root.left != null) {
res.addAll(preorderTraversal(root.left));
}
if (root.right != null) {
res.addAll(preorderTraversal(root.right));
}
return res;
}
中序遍历
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
if (root.left != null) {
res.addAll(inorderTraversal(root.left));
}
res.add(root.val);
if (root.right != null) {
res.addAll(inorderTraversal(root.right));
}
return res;
}
后序遍历
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
if (root.left != null) {
res.addAll(postorderTraversal(root.left));
}
if (root.right != null) {
res.addAll(postorderTraversal(root.right));
}
res.add(root.val);
return res;
}
层序遍历
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return res;
}
helper(root, 0);
return res;
}
private void helper(TreeNode root, int level) {
if (level == res.size()) {
res.add(new ArrayList<>());
}
res.get(level).add(root.val);
if (root.left != null) {
helper(root.left, level+1);
}
if (root.right != null) {
helper(root.right, level+1);
}
}
最大深度
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
最大直径
int maxd = 0;
public int diameterOfBinaryTree(TreeNode root) {
if (root == null) {
return 0;
}
depth(root);
return maxd;
}
private int depth(TreeNode root) {
if (root == null) {
return 0;
}
int left = depth(root.left);
int right = depth(root.right);
maxd = Math.max(left+right, maxd);
return Math.max(left, right) + 1;
}
