[toc]
二叉树Book
🌟 树的遍历
// 递归写法
List<Integer> list = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if(root != null) {
list.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
}
return list;
}
模板
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null)
return list;
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while(node!= null || !stack.isEmpty()) {
while(node != null ){
stack.push(node);
node = node.left;
}
......
}
return list;
}
1. 前序遍历
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null)
return list;
Stack<TreeNode> stack = new Stack<>();
while(root != null || !stack.isEmpty()) {
while(root != null) {
stack.push(root);
list.add(root.val);
root = root.left;
}
if(!stack.isEmpty()){
root = stack.pop();
root = root.right;
}
}
return list;
}
2. 中续遍历
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null)
return list;
Stack<TreeNode> stack = new Stack<>();
while(root!= null || !stack.isEmpty()) {
while(root != null ){
stack.push(root);
root = root.left;
}
if(!stack.isEmpty()){
root = stack.pop();
list.add(root.val);
root = root.right;
}
}
return list;
}
3. 后续遍历
注意 node.right == null || node.right == visited
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null)
return list;
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root, visited = root;
while(node!=null || !stack.isEmpty()) {
while(node != null) {
stack.push(node);
node = node.left;
}
node = stack.peek();
if(node.right == null || node.right == visited) {
stack.pop();
list.add(node.val);
visited = node;
node = null;
} else {
node = node.right;
}
}
return list;
}
4. 层续遍历
思路：利用队列实现
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null)
return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
int size = queue.size();
List<Integer> list = new ArrayList<>();
for(int i = 0 ; i < size; i++) {
TreeNode node = queue.poll();
list.add(node.val);
if(node.left != null)
queue.offer(node.left);
if(node.right != null)
queue.offer(node.right);
}
res.add(list);
}
return res;
}
🌟 递归解决问题
二叉树最大深度
// 自底向上
public int maxDepth(TreeNode root) {
if(root == null)
return 0;
return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
}
自顶向下方法
int res = 0;
// 自顶向下
public int maxDepth(TreeNode root) {
if(root == null) {
return 0;
}
max(root, 1);
return res;
}
private void max(TreeNode node, int answer) {
if(node == null)
return;
if(node.left == null && node.right == null){
res = Math.max(res, answer);
}
max(node.left, answer + 1);
max(node.right, answer + 1);
}
对称二叉树
注意 node1 == null && node2 == null 判断
class Solution {
public boolean isSymmetric(TreeNode root) {
return isSymmetric(root,root);
}
boolean isSymmetric(TreeNode node1, TreeNode node2) {
if(node1 == null && node2 == null)
return true;
if(node1 == null)
return false;
if(node2 == null)
return true;
if(node1.val != node2.val) {
return false;
}
return isSymmetric(node1.left, node2.right) && isSymmetric(node1.right, node2.left);
}
}
🌟 路径总和
注意
a) curSum传递
b) if(node == null) return false;
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root == null)
return false;
return getSum(root,targetSum);
}
boolean getSum(TreeNode node, int targetSum) {
if(node == null)
return false;
targetSum -= node.val;
if(targetSum == 0 && node.left == null && node.right == null) {
return true;
}
return getSum(node.left, targetSum) || getSum(node.right, targetSum);
}
🌟 从中序与后序遍历序列构造二叉树
注意，return null && 边界不要算node
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return buildTree(inorder,0, inorder.length-1, postorder,0 , postorder.length-1);
}
public TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart,
int postEnd) {
if(inStart > inEnd || postStart > postEnd)
return null;
// 根节点
TreeNode node = new TreeNode(postorder[postEnd]);
for(int i = inStart;i<= inEnd;i++){
// 找到中序的根节点，分隔左右子树
if(inorder[i] == postorder[postEnd]){
// 取左子树递归构造
node.left = buildTree(inorder, inStart, i - 1, postorder, postStart, postStart + i - inStart-1);
node.right = buildTree(inorder, i + 1 , inEnd, postorder, postStart + i - inStart, postEnd-1);
}
}
return node;
}
}
从前序与中序遍历序列构造二叉树
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTree(preorder, 0, preorder.length - 1, inorder , 0, inorder.length - 1);
}
public TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
if(preStart > preEnd || inStart > inEnd)
return null;
TreeNode node = new TreeNode(preorder[preStart]);
for(int i = inStart;i <= inEnd; i++) {
if(inorder[i]==preorder[preStart]) {
node.left = buildTree(preorder, preStart+ 1, preStart + i - inStart, inorder,inStart,i-1);
node.right = buildTree(preorder, preStart + 1 + i - inStart, preEnd, inorder,i+1,inEnd);
}
}
return node;
}
🌟 填充每个节点的下一个右侧节点指针
思路: 基于层续遍历
class Solution {
public Node connect(Node root) {
if(root == null)
return root;
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
int size = queue.size();
Node lastNode = null;
for(int i = 0; i < size; i++) {
Node node = queue.poll();
if(lastNode != null) {
lastNode.next = node;
}
lastNode = node;
if(node.left != null)
queue.offer(node.left);
if(node.right != null)
queue.offer(node.right);
}
}
return root;
}
}
填充每个节点的下一个右侧节点指针 II
class Solution {
public Node connect(Node root) {
if(root == null)
return root;
// 每次初始指向上一排的第一个链表
Node cur = root;
while(cur != null){
// 第一个空节点
Node pre = new Node(0);
// 使用 node 串联
Node node = pre;
while(cur != null) {
if(cur.left != null){
node.next = cur.left;
node = node.next;
}
if(cur.right != null){
node.next = cur.right;
node = node.next;
}
cur = cur.next;
}
// 指回该行第一个
cur = pre.next;
}
return root;
}
}
🌟 二叉树的最近公共祖先
思路：
a) 递归把所有节点放入map
b) 把p节点的祖先们放入visited
c）找q结点祖先和p重合
class Solution {
private HashMap<Integer,TreeNode> map = new HashMap<>();
private List<Integer> visited = new ArrayList<>();
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
getParents(root);
// 找p节点的祖先们，放入visited
TreeNode cur = p;
while (cur != null) {
visited.add(cur.val);
// cur再找亲爸爸
cur = map.get(cur.val);
}
cur = q;
while (cur != null) {
// 如果发现当前节点和p祖先们【visited】有重合
if(visited.contains(cur.val)) {
return cur;
}
// cur再找亲爸爸
cur = map.get(cur.val);
}
return null;
}
public void getParents(TreeNode root) {
if(root.left==null && root.right==null)
return;
if(root.left!=null){
map.put(root.left.val,root);
getParents(root.left);
}
if(root.right!=null){
map.put(root.right.val,root);
getParents(root.right);
}
}
}
🌟 二叉树的序列化与反序列化
Tips: 递归
序列化：
root=null 为 #， 使用递归添加到StringBuilder中反序列化：队列 + 递归
- 将string进行分隔后加入队列
- 使用递归进行还原
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root == null)
return "#,";
StringBuilder res = new StringBuilder(root.val + ",");
res.append(serialize(root.left));
res.append(serialize(root.right));
return res.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data == null || data == "#,")
return null;
String[] ss = data.split(",");
Queue<String> queue = new LinkedList<>();
for(String s: ss)
queue.offer(s);
return pre(queue);
}
TreeNode pre(Queue<String> queue) {
String val = queue.poll();
if (val.equals("#"))
return null;
TreeNode node = new TreeNode(Integer.parseInt(val));
node.left = pre(queue);
node.right = pre(queue);
return node;
}
}
