二叉树
遍历
遍历分两种
广度优先遍历
尽可能先访问距离根节点最近的节点，也称之为层序遍历。
深度优先遍历
对于二叉树，进一步分为三种
- 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;}@Overridepublic 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;
}
}