概述
二叉树的定义：
private static class TreeNode {
private TreeNode left;
private TreeNode right;
private final int val;
TreeNode(int x) {
this.val = x;
}
}
遍历
二叉树的遍历方式有很多，
层序遍历
后序遍历+迭代
public static List<Integer> postOrderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> nodeStack = new Stack<>();
TreeNode nodeTemp = root;
TreeNode preNode = null;
while (nodeTemp != null || !nodeStack.isEmpty()) {
while (nodeTemp != null) {
nodeStack.push(nodeTemp);
nodeTemp = nodeTemp.left;
}
nodeTemp = nodeStack.peek();
if (nodeTemp.right == null || nodeTemp.right == preNode) {
nodeTemp = nodeStack.pop();
list.add(nodeTemp.val);
preNode = nodeTemp;
nodeTemp = null;
} else {
nodeTemp = nodeTemp.right;
}
}
return list;
}
求一棵树所有左叶子节点的和
左叶子的定义，递归找到所有的子树的左叶子节点。
如果二叉树的左子树是叶子节点，要找的就是它。
如果二叉树的左子树不是一个叶子节点，则递归调用此过程去获取左子树的左叶子节点的值。
二叉树的右子树，递归调用获取右子树的左叶子节点值即可。
public class SumOfLeftLeaves {
/**
* 递归方式
*/
public static int sumOfLeftLeaves(TreeNode root) {
// 递归结束条件
if (root == null) {
return 0;
}
int left, right;
if (root.left != null && root.left.left == null && root.left.right == null) {
// 判断是否为左叶子节点
left = root.left.val;
} else {
left = sumOfLeftLeaves(root.left);
}
right = sumOfLeftLeaves(root.right);
return left + right;
}
/**
* 前序遍历迭代方式
*/
public static int sumOfLeftLeavesByPreOrder(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
int sum = 0;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
if (root.left != null && root.left.left == null && root.left.right == null) {
sum += root.left.val;
}
root = root.left;
}
if (!stack.isEmpty()) {
root = stack.pop().right;
}
}
return sum;
}
/**
* 层级遍历二叉树,层序遍历,广度遍历
*/
public static int sumOfLeftLeavesByLevelOrder(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new ArrayDeque<>();
int sum = 0;
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node.left != null && node.left.left == null && node.left.right == null) {
sum += node.left.val;
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return sum;
}
/**
* 层次遍历
*/
public static void levelOrderTraversal(TreeNode node) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(node);
while (!queue.isEmpty()) {
node = queue.poll();
System.out.print(node.val + " ");
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
}
从中序与后序遍历序列构造二叉树
public static TreeNode buildTree(int[] inOrder, int[] postOrder) {
return helper(inOrder, postOrder, postOrder.length - 1, 0, inOrder.length - 1);
}
private static 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 int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int deep = 1;
if (root.left == null && root.right == null) {
return 1;
}
int leftDeep = 0;
if (root.left != null) {
leftDeep = 1 + maxDepth(root.left);
}
int rightDeep = 0;
if (root.right != null) {
rightDeep = 1 + maxDepth(root.right);
}
return deep + leftDeep > rightDeep ? leftDeep : rightDeep;
}
简化版：
public static int maxDepth1(TreeNode root) {
if (root == null) {
return 0;
}
// 注意要+1
return Math.max(maxDepth1(root.left), maxDepth1(root.right)) + 1;
}
平衡二叉树
判断给定的二叉树是否是一颗平衡树。平衡树的定义是左右子树的高度差不超过1。
public static 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);
}
将有序数组转换为二叉搜索树
给定一个升序排序的整数数组 nums，将其转换为一棵高度平衡的二叉搜索树。
分析：给定一个有序数组，转换成二叉搜索树，即左子树小于根节点，根节点小于右子树，满足条件的二叉搜索树显然不止一种。
public static TreeNode sortedArrayToBST(int[] nums) {
return traversal(nums, 0, nums.length - 1);
}
public static TreeNode traversal(int[] nums, int left, int right) {
if (left > right){
return null;
}
int mid = left + ((right - left) / 2);
TreeNode node = new TreeNode(nums[mid]);
node.left = traversal(nums, left, mid - 1);
node.right = traversal(nums, mid + 1, right);
return node;
}
二叉树求和路径
给定一个二叉树，和一个整数sum，求路径和为sum的方案。
分析：路径指的是从根节点到叶子节点，每次可以选择左子树或右子树。假如sum过小或过大，则不存在这样的路径；有时，存在不止一条路径。
public static List<List<Integer>> pathSum(TreeNode root, int sum) {
if (root == null) {
return new ArrayList<>();
}
List<List<Integer>> ans = new ArrayList<>();
if (root.val == sum && root.left == null && root.right == null) {
List<Integer> arr = new ArrayList<>();
arr.add(root.val);
ans.add(arr);
return ans;
}
List<List<Integer>> left = pathSum(root.left, sum - root.val);
List<List<Integer>> right = pathSum(root.right, sum - root.val);
for (List<Integer> list : left) {
list.add(0, root.val);
ans.add(list);
}
for (List<Integer> list : right) {
list.add(0, root.val);
ans.add(list);
}
return ans;
}
二叉树中的最大路径和
二叉树的右视图
右视图的定义：从右侧看一棵树，从上到下看到的右叶子节点序列。
public static List<Integer> rightSideView(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
list.add(root.val);
List<Integer> list1 = rightSideView(root.right);
List<Integer> list2 = rightSideView(root.left);
list.addAll(list1);
if (list1.size() < list2.size()) {
for (int i = list1.size(); i < list2.size(); i++) {
list.add(list2.get(i));
}
}
return list;
}
序列化
思路和层序遍历没有多大差别：
public static String serialize(TreeNode root) {
if (root == null) {
return "[]";
}
ArrayList<TreeNode> queue = new ArrayList<>();
queue.add(root);
for (int i = 0; i < queue.size(); i++) {
TreeNode node = queue.get(i);
if (node == null) {
continue;
}
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
while (queue.get(queue.size() - 1) == null) {
queue.remove(queue.size() - 1);
}
StringBuilder sb = new StringBuilder();
sb.append("[");
sb.append(queue.get(0));
for (int i = 1; i < queue.size(); i++) {
if (queue.get(i) == null) {
sb.append(",");
sb.append("null");
} else {
sb.append(",");
sb.append(queue.get(i).val);
}
}
sb.append("]");
return sb.toString();
}
