二叉树
遍历
遍历分两种
广度优先遍历
尽可能先访问距离根节点最近的节点，也称之为层序遍历。
深度优先遍历
对于二叉树，进一步分为三种
- pre-order前序遍历，对于每一颗子树，先访问该节点，然后是左子树，最后是右子树；
- in-order中序遍历，对于每一颗子树，先访问左子树，然后是该节点，最后是右子树；
- post-order后序遍历，对于每一颗子树，先访问左子树，然后是右子树，最后是该节点；
使用递归方式实现
前序遍历
public class TreeNode{
TreeNode left;
int value;
TreeNode right;
public TreeNode() {
}
public TreeNode(TreeNode left, int value, TreeNode) {
this.left = left;
this.value = value;
this.right = right;
}
@Override
public String toString() {
return String.valueOf(this.value);
}
}
public class TreeTraversal{
public static void main(String[] args) {
TreeNode root = new TreeNode(
new TreeNode(new TreeNode(4, 2, null)),
1,
new TreeNode(new TreeNode(5, 3, new TreeNode(6))));
}
public void preOrder(TreeNode node) {
if (node == null) {
return;
}
System.out.println(node.value + "\t"); // 值
preOrder(node.left); // 左
preOrder(node.right); // 右
}
public void inOrder(TreeNode node) {
if (node == null) {
return;
}
preOrder(node.left); // 左
System.out.println(node.value + "\t"); // 值
preOrder(node.right); // 右
}
public void postOrder(TreeNode node) {
if (node == null) {
return;
}
preOrder(node.left); // 左
preOrder(node.right); // 右
System.out.println(node.value + "\t"); // 值
}
}
非递归实现
前序遍历和中序遍历
public class TreeTraversal{
public static void main(String[] args) {
TreeNode root = new TreeNode(
new TreeNode(new TreeNode(4, 2, null)),
1,
new TreeNode(new TreeNode(5, 3, new TreeNode(6))));
Stack<Integer> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
if (curr != null) {
System.out.println(curr.value); // 前序遍历
stack.push(curr);
curr = curr.left;
} else {
TreeNode pop = stack.pop();
System.out.println(pop.value); // 中序遍历
curr = pop.right;
}
}
}
}
后序遍历
public class TreeTraversal{
public static void main(String[] args) {
TreeNode root = new TreeNode(
new TreeNode(new TreeNode(4, 2, null)),
1,
new TreeNode(new TreeNode(5, 3, new TreeNode(6))));
Stack<Integer> stack = new Stack<>();
TreeNode curr = root;
TreeNode pop = null;
while (curr != null || !stack.isEmpty()) {
if (curr != null) {
stack.push(curr);
curr = curr.left;
} else {
TreeNode peek = stack.peek();
if (peek.right == null || peek.right == peek) {
pop = stack.pop();
System.out.println(pop.value); // 后序遍历
} else {
curr = peek.right;
}
}
}
}
}
同时实现前序遍历、中序遍历和后序遍历
public class TreeTraversal{
public static void main(String[] args) {
TreeNode root = new TreeNode(
new TreeNode(new TreeNode(4, 2, null)),
1,
new TreeNode(new TreeNode(5, 3, new TreeNode(6))));
Stack<Integer> stack = new Stack<>();
TreeNode curr = root; // 当前节点
TreeNode pop = null; // 最近一次弹栈节点
while (curr != null || !stack.isEmpty()) {
if (curr != null) {
stack.push(curr);
// 待处理左子树
System.out.println(curr.value); // 前序遍历
curr = curr.left;
} else {
TreeNode peek = stack.peek();
// 无右子树
if (peek.right == null) {
System.out.println(peek.value); // 中序遍历
pop = stack.pop();
System.out.println(pop.value); // 后序遍历
}
// 右子树处理完成
else if (peek.right == peek) {
pop = stack.pop();
System.out.println(pop.value); // 后序遍历
}
// 待处理右子树
else {
System.out.println(peek.value); // 中序遍历
curr = peek.right;
}
}
}
}
}
Leetcode
Leetcode101对称二叉树
public class Leetcode101{
public boolean isSymmetric(TreeNode root) {
return check(root.left, root.right);
}
public boolean check(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (right == null || left == null) {
return false;
}
if (left.value != right.value) {
return false;
}
return check(left.left, right.right) && check(left.right, right.left);
}
}
Leetcode104最大深度
方法一
使用递归
public class Leetcode104{
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
int i = maxDepth(root.left);
int j = maxDepth(root.right);
return Math.max(i, j) + 1;
}
}
方法二
使用后序遍历
public class Leetcode104{
public int maxDepth(TreeNode root) {
TreeNode curr = root;
Stack<TreeNode> stack = new Stack<>();
TreeNode pop = null; // 最近一次弹栈元素/节点
int max = 0; // 栈的最大深度
while(curr != null || !stack.isEmpty()) {
if (curr != null) {
stack.push(curr);
if (stack.size() > max) {
max = stack.size();
}
curr = curr.next;
} else {
TreeNode peek = stack.peek();
if (peek.right == null || peek.right == pop) {
pop = stack.pop();
} else {
curr = peek.right;
}
}
}
}
}
方法三
使用层序遍历
public class Leetcode104{
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int depth = 0;
while(!queue.isEmpty()) {
int size = queue.size(); // 写在循环内，需要多次调用，所以写在循环外
for(int i = 0; i < size; i++) {
TreeNode poll = queue.poll();
if (poll.left != null) {
queue.offer(poll.left);
}
if (poll.right != null) {
queue.offer(poll.right);
}
}
depth++;
}
return depth;
}
}
Leetcode111二叉树最小深度
方法一
public class Leetcode111{
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
int d1 = minDepth(root.left);
int d2 = minDepth(root.right);
if (d1 == 0) { // 当左子树为空
return d2 + 1;
}
if (d2 == 0) { // 当右子树为空
return d1 + 1;
}
return Math.min(d1, d2) + 1;
}
}
方法二
使用层序遍历实现，找到第一个叶子节点，求得最小深度
public class Leetcode111{
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
LinkedList<TreeNode> queue = new LinkedList<>(); // LinkedList可以作为双向链表、队列、栈
queue.offer(root);
int c1 = 1;
int depth = 0;
while (!queue.isEmpty()) {
int c2 = 0;
depth++;
for(int i = 0; i < c1; i++) {
TreeNode poll = queue.poll();
if (poll.left == null && poll.right == null) {
return depth;
}
if (poll.left != null) {
queue.offer(poll.left);
c2++;
}
if (poll.right != null) {
queue.offer(poll.right);
c2++;
}
}
c1 = c2;
}
return depth;
}
}
Leetcode226
二叉树反转
public class Leetcode226{
public TreeNode invertTree(TreeNode root) {
if (root == null ||(root.left == null && root.right == null)) {
return root;
}
fn(root);
return root;
}
public void fn(TreeNode node) {
if (node == null) {
return;
}
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
fn(node.left);
fn(node.right);
}
}
后缀表达式构建二叉树
中缀表达式 (2 - 1) * 3
后缀表达式/逆波兰表达式 21-3*
表达树
*
/ \
- 3
/ \
2 1
public class ExpressionTree{
public TreeNode constructExpressionTree (String[] tokens){
Stack<TreeNode> stack = new Stack<>();
for(String t : tokens) {
switch (t) {
case "+", "-", "*", "/" -> { // 运算符
TreeNode right = stack.pop();
TreeNode left = stack.pop();
TreeNode parent = new TreeNode(t);
parent.left = left;
parent.right = right;
stack.push(parent);
}
default -> { // 数字
stack.push(new TreeNode(t));
}
}
}
return stack.peek();
}
}
Leetcode105
根据前序遍历和中序遍历，得到二叉树
public class Leetcode105{
public TreeNode buildTree(int[] preOrder, int inOrder) {
if (preOrder.length == 0) {
return null;
}
// 创建根节点
int rootValue = preOrder[0];
TreeNode root = new TreeNode(rootValue);
for(int i = 0; i < inOrder.length; i++) {
if (inOrder[i] == rootValue) {
int[] inLeft = Arrays.copyOfRange(inOrder, 0, i);
int[] inRight = Arrays.copyOfRange(inOrder, i + 1, inOrder.length);
int[] preLeft = preLeftArrays.copyOfRange(preOrder, 1, i + 1);
int[] preRight = Arrays.copyOfRange(preOrder, i + 1, preOrder.length);
root.left = buildTree(preLeft, inLeft);
root.right = buildTree(preRight, inRight);
break;
}
}
return root;
}
}
Leetcode106
根据中序遍历和后序遍历得到二叉树
public class Leetcode106{
public TreeNode buildTree(int[] inOrder, int postOrder) {
if (postOrder.length == 0) {
return null;
}
// 创建根节点
int rootValue = postOrder[postOrder.length - 1];
TreeNode root = new TreeNode(rootValue);
for(int i = 0; i < inOrder.length; i++) {
if (inOrder[i] == rootValue) {
int[] inLeft = Arrays.copyOfRange(inOrder, 0, i);
int[] inRight = Arrays.copyOfRange(inOrder, i + 1, inOrder.length);
int[] postLeft = preLeftArrays.copyOfRange(preOrder, 0, i);
int[] postRight = Arrays.copyOfRange(preOrder, i, preOrder.length - 1);
root.left = buildTree(inLef, tpostLeft);
root.right = buildTree(inRight, postRight);
break;
}
}
return root;
}
}
int[] inRight = Arrays.copyOfRange(inOrder, i + 1, inOrder.length);
int[] postLeft = preLeftArrays.copyOfRange(preOrder, 0, i);
int[] postRight = Arrays.copyOfRange(preOrder, i, preOrder.length - 1);
root.left = buildTree(inLef, tpostLeft);
root.right = buildTree(inRight, postRight);
break;
}
}
return root;
}
}
