树的基础算法总结
树的遍历算法
二叉树结点
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
N叉树结点
static class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
}
二叉树遍历
- 先序
- 中序
- 后序
递归 和 非 递归 算法
【注， 后序的非递归算法 和 先序 思路相反】
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class TraverseTree {
// 先序遍历， 非递归
// 利用堆栈
public static void preOrderUnRecur(Node head) {
System.out.print("先序 非递归: ");
if (head != null) {
Stack<Node> stack = new Stack<Node>();
stack.push(head);
while (!stack.isEmpty()) {
head = stack.pop();
System.out.print(head.data + " ");
if (head.right != null) { // 有右先压右
stack.push(head.right);
}
if (head.left != null) { // 有左后压左
stack.push(head.left);
}
}
}
System.out.println();
}
// 中序遍历 非递归
public static void inOrderUnRecur(Node head) {
System.out.print("先序 非递归: ");
Deque<Node> stack = new LinkedList<Node>();
while (!stack.isEmpty() || head != null) {
// 左边界进栈
while (head != null) {
stack.push(head);
head = head.left;
}
head = stack.pop();
System.out.print(head.data + " ");
// head 到右子树上去
head = head.right;
}
System.out.println();
}
// 层序遍历 非递归
//利用队列
public static void seqOrdUnRecur(Node head) {
System.out.print("层序 非递归: ");
if (head != null) {
Queue<Node> queue = new LinkedList<Node>();
queue.add(head); //
while (!queue.isEmpty()) { // 队列为空时，结束遍历
head = queue.poll(); // 出队列
System.out.print(head.data + " ");
// 左右孩子分别入队列
if(head.left != null) {
queue.add(head.left);
}
if(head.right != null) {
queue.add(head.right);
}
}
}
System.out.println();
}
// 先序遍历 递归
public static void preOrderRecur(Node head) {
if (head == null) {
return;
}
System.out.print(head.data + " ");
preOrderRecur(head.left);
preOrderRecur(head.right);
}
// 中序遍历 递归
public static void inOrderRecur(Node head) {
if (head == null) {
return;
}
inOrderRecur(head.left);
System.out.print(head.data + " ");
inOrderRecur(head.right);
}
// 获取每层数值之和，（中序，后序，先序 思路相同）
int[] levelSum = new int[n];
public void inorder(TreeNode node, int level) {
if (node != null) {
inorder(node.left, level + 1);
levelSum[level] += node.val;
inorder(node.right, level + 1);
}
}
// 后序遍历 递归
public static void posOrderRecur(Node head) {
if (head == null) {
return;
}
posOrderRecur(head.left);
posOrderRecur(head.right);
System.out.print(head.data + " ");
}
}
二叉树深度
/**
* 递归
* 时间复杂度：O(n)，其中 nn 为二叉树节点的个数。每个节点在递归中只被遍历一次。
* 空间复杂度：O(height)，其中 height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。
*/
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int right = maxDepth(root.right);
int left = maxDepth(root.left);
return right > left ? right + 1 : left + 1;
}
/**
* 非递归： 广度优先搜索
* 时间复杂度：O(n)，其中 n 为二叉树的节点个数。与方法一同样的分析，每个节点只会被访问一次。
* 空间复杂度：此方法空间的消耗取决于队列存储的元素数量，其在最坏情况下会达到 O(n)。
*/
public int maxDepth2(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int ans = 0;
while (!queue.isEmpty()) {
int size = queue.size();
while (size > 0) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
size--;
}
ans++;
}
return ans;
}
N 叉树深度
/**
* 递归
*/
public int maxDepth(Node root) {
if (root == null) {
return 0;
}
int max = 0;
for (Node node : root.children) {
int height = maxDepth(node);
if (max < height) {
max = height;
}
}
return max + 1;
}
N 叉树遍历
N 叉树的前序遍历
public class Main589 {
static List<Integer> list = new LinkedList<>();
/**
* 递归
* @param root
* @return
*/
public List<Integer> preorder(Node root) {
if (root == null) {
return list;
}
list.add(root.val);
for (Node node: root.children) {
preorder(node);
}
return list;
}
}
N 叉树的后序遍历
public class Main590 {
List<Integer> list = new ArrayList<>();
/**
* 递归
*/
public List<Integer> postorder(Node root) {
if (root == null) {
return list;
}
for (Node node : root.children) {
postorder(node);
}
list.add(root.val);
return list;
}
}
二叉树
合并二叉树
/**
* 递归
*/
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
// 1.合并当前节点
// t1没有，而t2有的节点，直接返回t2
if (t1 == null) {
return t2;
}
// t1有，而t2没有的节点，t1不变，直接返回
if (t2 == null) {
return t1;
}
// t1和t2都有的节点，节点值相加，更新t1的值
t1.val += t2.val;
// 2.递归合并左子树和右子树
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
}
平衡二叉树
判断是否是平衡二叉树
public class Main110 {
// 递归调用
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
} else {
return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
}
public int height(TreeNode root) {
if (root == null) {
return 0;
} else {
int left = height(root.left);
int right = height(root.right);
return left > right ? left+1 : right+1;
}
}
}
将有序数组转换为二叉搜索树
public TreeNode sortedArrayToBST(int[] nums) {
return helper(nums, 0, nums.length - 1);
}
public TreeNode helper(int[] nums, int left, int right) {
if (left > right) {
return null;
}
// 总是选择中间位置左边的数字作为根节点
int mid = (left + right) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums, left, mid - 1);
root.right = helper(nums, mid + 1, right);
return root;
}
将二叉搜索树变平衡
方法一： 中序遍历二叉搜索树， 将获得的有序数组 按照 上述方法转化