定义一个二叉树
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode next;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
TreeNode(int _val, TreeNode _left, TreeNode _right, TreeNode _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
}
一、二叉树遍历
1. 前序遍历
前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。
public class PreorderTraversal {
private List ans;
public List preorderTraversal(TreeNode root) {
ans = new ArrayList<>();
dfs(root);
return ans;
}
public void dfs(TreeNode root) {
if (root == null) {
return;
}
ans.add(root.val);
dfs(root.left);
dfs(root.right);
}
public List preorderTraversal1(TreeNode root) {
ans = new ArrayList<>();
// 根节点为空，直接返回
if (root == null) {
return ans;
}
// 创建栈
Deque stack = new linkedList();
//根节点复制一份传给node, node表示当前节点
TreeNode node = root;
// 当栈不为空或者node不为空时，继续循环
while (!stack.isEmpty() || node != null) {
// 当前节点不为空时，继续从左子树向下循环
while (node != null){
ans.add(node.val);
stack.push(node);
node = node.left;
}
node = stack.pop();
node = node.right;
}
return ans;
}
}
Deque.pop()：从此双端队列所表示的堆栈中弹出一个元素。Deque.push()：将一个元素推入此双端队列表示的栈中，即从此双端队列的头部添加元素。 2. 中序遍历
中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。
public class InorderTraversal {
private List ans;
public List inorderTraversal(TreeNode root) {
ans = new ArrayList<>();
dfs(root);
return ans;
}
public void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
ans.add(root.val);
dfs(root.right);
}
public List inorderTraversal1(TreeNode root) {
ans = new ArrayList<>();
// 空树判断
if (root == null) {
return ans;
}
// 利用双端队列创建一个栈
Deque stack = new linkedList();
TreeNode node = root;
// 栈不为空或节点不为空则继续循环。
while (!stack.isEmpty() || node != null) {
while (node != null) {
// 节点入栈
stack.push(node);
// 向左走，当没有左子树时跳出循环。
node = node.left;
}
node = stack.pop();
ans.add(node.val);
node = node.right;
}
return ans;
}
}
3. 后序遍历
后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。
public class PostorderTraversal {
private List ans;
public List postorderTraversal(TreeNode root) {
ans = new ArrayList<>();
dfs(root);
return ans;
}
public void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
dfs(root.right);
ans.add(root.val);
}
public List postorderTraversal1(TreeNode root) {
ans = new ArrayList<>();
// 根节点为空，直接返回
if (root == null) {
return ans;
}
// 创建栈
Deque stack = new linkedList();
//根节点复制一份传给node, node表示当前节点
TreeNode node = root;
// 当栈不为空或者node不为空时，继续循环
while (!stack.isEmpty() || root != null) {
// 当前节点不为空时，继续从左子树向下循环
while (root != null) {
stack.push(root);
root = root.left;
}
// 将最左边的节点取出来，然后判断它有没有右子树，以及
root = stack.pop();
if (root.right == null || root.right == node) {
ans.add(root.val);
node = root;
root = null;
} else {
stack.push(root);
root = root.right;
}
}
return ans;
}
}
4. 层序遍历
即逐层地，从左到右访问所有节点。
public class LevelOrderTraversal {
private List> ans;
public List> levelOrder(TreeNode root) {
ans = new ArrayList<>();
dfs(ans, root, 0);
return ans;
}
public void dfs(List> ans, TreeNode root, int level) {
// 边界条件判断
if (root == null) {
return;
}
// level代表层数，如果 level >= list.size()，说明到下一层了，所以要先把下一层的list初始化，防止下面的add的时候空指针异常。
if (level >= ans.size()) {
ans.add(new ArrayList<>());
}
// level并表示的是第几层，这里访问到第几层，就把数据加入到第几层
ans.get(level).add(root.val);
// 当前节点访问完之后，在使用递归的方式分别访问当前节点的左右子节点。
dfs(ans, root.left, level + 1);
dfs(ans, root.right, level + 1);
}
public List> levelOrder1(TreeNode root) {
ans = new ArrayList>();
// 根节点为空直接返回
if (root == null) {
return ans;
}
// 创建一个队列进行存储节点数据。
Queue queue = new linkedList();
// 根节点入队列
queue.add(root);
while (!queue.isEmpty()) {
// 此列表存储每一层的数据
ArrayList level = new ArrayList<>();
// 每一层的数据个数
int levelCount = queue.size();
for (int i = 0; i < levelCount; i++) {
// 节点出队
TreeNode node = queue.remove();
// 左节点入队
if (node.left != null) {
queue.add(node.left);
}
// 右节点入队
if (node.right != null) {
queue.add(node.right);
}
level.add(node.val);
}
ans.add(level);
}
return ans;
}
}
二、运用递归解决问题
1. 二叉树的最大深度
public class MaxDepth {
public int maxDepthDFSRecursion(TreeNode root) {
if (root == null) {
return 0;
} else {
// 获取左子树的深度
int leftHeight = maxDepthDFSRecursion(root.left);
// 获取右子树的深度
int rightHeight = maxDepthDFSRecursion(root.right);
// 返回其左右子树最大深度加1
return Math.max(leftHeight, rightHeight) + 1;
}
}
public int maxDepthDFSNonRecursion(TreeNode root) {
// 记录二叉树的最大深度
int max = 0;
if (root == null) {
return max;
}
// 节点栈
Stack nodeStack = new Stack();
// 节点层数栈
Stack levelStack = new Stack();
nodeStack.push(root);
levelStack.push(1);
while (!nodeStack.empty()) {
// 弹出节点与其对应的层数
TreeNode curNode = nodeStack.pop();
int curNodelevel = levelStack.pop();
// 记录最大层数
max = Math.max(max, curNodelevel);
// 因为是前序遍历（根-左-右），所以右子树先入栈。
if (curNode.right != null) {
nodeStack.push(curNode.right);
levelStack.push(curNodelevel + 1);
}
if (curNode.left != null) {
nodeStack.push(curNode.left);
levelStack.push(curNodelevel + 1);
}
}
return max;
}
public int maxDepthBFS(TreeNode root){
List> ans = new ArrayList<>();
dfs(ans, root, 0);
return ans.size();
}
public void dfs(List> ans, TreeNode root, int level) {
// 边界条件判断
if (root == null) {
return;
}
// level代表层数，如果 level >= list.size()，说明到下一层了，所以要先把下一层的list初始化，防止下面的add的时候空指针异常。
if (level >= ans.size()) {
ans.add(new ArrayList<>());
}
// level并表示的是第几层，这里访问到第几层，就把数据加入到第几层
ans.get(level).add(root.val);
// 当前节点访问完之后，在使用递归的方式分别访问当前节点的左右子节点。
dfs(ans, root.left, level + 1);
dfs(ans, root.right, level + 1);
}
public int maxDepthBFSNonRecursion(TreeNode root) {
if (root == null) {
return 0;
}
Deque stack = new linkedList();
stack.add(root);
TreeNode outNode = root;
// count 记录二叉树的深度
int count = 1;
while (!stack.isEmpty()) {
// 记录每一层节点的个数；
int levelCount = stack.size();
// outNode为栈队列出队的节点
for (int i = 0; i < levelCount; i++) {
outNode = stack.pop();
if (outNode.left != null) {
stack.add(outNode.left);
}
if (outNode.right != null) {
stack.add(outNode.right);
}
}
count++;
}
return count;
}
}
2. 对称二叉树
public class IsSymmetric {
public boolean isSymmetric3(TreeNode root) {
return dfs3(root, root);
}
public boolean dfs3(TreeNode p,TreeNode q) {
if(p == null && q == null){
return true;
}
if(p == null || q == null){
return false;
}
return p.val == q.val && dfs3(p.left,q.right) && dfs3(p.right,q.left);
}
public boolean isSymmetric4(TreeNode root){
Queue nodeQueue = new linkedList();
// 根节点入队两次
nodeQueue.add(root);
nodeQueue.add(root);
while (!nodeQueue.isEmpty()){
TreeNode leftNode = nodeQueue.remove();
TreeNode rightNode = nodeQueue.remove();
if(leftNode == null && rightNode == null){
continue;
}
if((leftNode == null || rightNode == null) || leftNode.val != rightNode.val){
return false;
}
nodeQueue.add(leftNode.left);
nodeQueue.add(rightNode.right);
nodeQueue.add(leftNode.right);
nodeQueue.add(rightNode.left);
}
return true;
}
public boolean isSymmetric1(TreeNode root) {
// 边界判断
if (root == null) {
return false;
}
// 存储根节点的左子树列表
ArrayList leftSubtree = new ArrayList();
// 存储根节点的左子树
ArrayList rightSubtree = new ArrayList();
dfs1(root.left, leftSubtree);
dfs2(root.right, rightSubtree);
// 若两个列表长度不同，则直接返回false
if (leftSubtree.size() != rightSubtree.size()) {
return false;
} else {
// 若相同，则循环遍历，当有不同的值时，返回false，完全相同则返回true
for (int i = 0; i < leftSubtree.size(); i++) {
if (leftSubtree.get(i) != rightSubtree.get(i)) {
return false;
}
}
return true;
}
}
public void dfs1(TreeNode root, List leftSubTree) {
if (root == null) {
leftSubTree.add(0);
return;
} else {
leftSubTree.add(root.val);
dfs1(root.left, leftSubTree);
dfs1(root.right, leftSubTree);
}
}
public void dfs2(TreeNode root, List rightSubTree) {
if (root == null) {
rightSubTree.add(0);
return;
} else {
rightSubTree.add(root.val);
dfs2(root.right, rightSubTree);
dfs2(root.left, rightSubTree);
}
}
public boolean isSymmetric2(TreeNode root) {
// 边界判断
if (root == null) {
return false;
}
// 将根节点分为左右子树
TreeNode leftSubtreeNode = root.left;
TreeNode rightSubtreeNode = root.right;
// 当左右子树都为空时，返回true
if (leftSubtreeNode == null && rightSubtreeNode == null) {
return true;
}
// 创建左右子树队列
Queue leftSubtreeNodeQueue = new linkedList();
Queue rightSubtreeNodeQueue = new linkedList();
leftSubtreeNodeQueue.add(leftSubtreeNode);
rightSubtreeNodeQueue.add(rightSubtreeNode);
// 当其中一个子树为空，另一个不为空时，返回false
if ((leftSubtreeNode == null && rightSubtreeNode != null) ||
(leftSubtreeNode != null && rightSubtreeNode == null)) {
return false;
}
while (!leftSubtreeNodeQueue.isEmpty() && !rightSubtreeNodeQueue.isEmpty()) {
leftSubtreeNode = leftSubtreeNodeQueue.remove();
rightSubtreeNode = rightSubtreeNodeQueue.remove();
// 节点出队，判断节点值是否相等，若不相等，则直接返回false
if (leftSubtreeNode.val == rightSubtreeNode.val) {
// 按照遍历顺序往队列中添加节点，当其中一个节点为空，另一个不为空时，返回false
if (leftSubtreeNode.left != null && rightSubtreeNode.right != null) {
leftSubtreeNodeQueue.add(leftSubtreeNode.left);
rightSubtreeNodeQueue.add(rightSubtreeNode.right);
} else if ((leftSubtreeNode.left != null && rightSubtreeNode.right == null) ||
(leftSubtreeNode.left == null && rightSubtreeNode.right != null)) {
return false;
}
if (leftSubtreeNode.right != null && rightSubtreeNode.left != null) {
leftSubtreeNodeQueue.add(leftSubtreeNode.right);
rightSubtreeNodeQueue.add(rightSubtreeNode.left);
} else if ((leftSubtreeNode.right != null && rightSubtreeNode.left == null) ||
(leftSubtreeNode.right == null && rightSubtreeNode.left != null)) {
return false;
}
} else {
return false;
}
// 当其中一个队列为空，另一个不为空时，返回false
if ((!leftSubtreeNodeQueue.isEmpty() && rightSubtreeNodeQueue.isEmpty()) ||
(leftSubtreeNodeQueue.isEmpty() && !rightSubtreeNodeQueue.isEmpty())) {
return false;
}
}
return true;
}
}
3. 路径总和
public class HasPathSum {
public boolean hasPathSum1(TreeNode root, int targetSum) {
// 当前节点为null时，返回false
if (root == null) {
return false;
}
// 判断当前节点是否是叶子节点，若是则判断值是否相等
if (root.left == null && root.right == null) {
return root.val == targetSum;
}
return hasPathSum1(root.left, targetSum - root.val) || hasPathSum1(root.right, targetSum - root.val);
}
public boolean hasPathSum2(TreeNode root, int targetSum) {
// 边界处理
if(root == null){
return false;
}
// 定义两个队列
Queue nodeQueue = new linkedList();
Queue pathSumQueue = new linkedList();
nodeQueue.add(root);
pathSumQueue.offer(root.val);
while (!nodeQueue.isEmpty()){
TreeNode curNode = nodeQueue.poll();
int curPathSum = pathSumQueue.poll();
// 判断是不是叶子节点，如果是，则进行比对
if(curNode.left == null && curNode.right == null){
if(curPathSum == targetSum){
return true;
}
}
if(curNode.left!=null){
nodeQueue.offer(curNode.left);
pathSumQueue.offer(curPathSum+curNode.left.val);
}
if(curNode.right!=null){
nodeQueue.offer(curNode.right);
pathSumQueue.offer(curPathSum+curNode.right.val);
}
}
return false;
}
}
三、总结
1. 从前序与中序遍历序列构造二叉树
public class PreorderAndInorderBuildTree {
// 创建成员变量，方便调用
private int post_idx;
private int[] preorder;
private int[] inorder;
private Map idx_map = new HashMap();
public TreeNode preorderAndInorderBuildTreeq1(int[] preorder, int[] inorder) {
// 初始化
this.preorder = preorder;
this.inorder = inorder;
post_idx = 0;
// 将中序遍历数组元素存入 idx_map
int idx = 0;
for (Integer val : inorder) {
idx_map.put(val, idx++);
}
return helper(0, inorder.length - 1);
}
private TreeNode helper(int in_left, int in_right) {
// 如果 in_left > in_right 说明当前子树为空，返回空
if (in_left > in_right) {
return null;
}
// 获取根结点的值，并建立根节点
int root_val = preorder[post_idx];
TreeNode root = new TreeNode(root_val);
// 根节点向右移动一位
post_idx++;
// 获取根节点在中序遍历数组中的 index
int index = idx_map.get(root_val);
// 递归建立左右子树，先创建左子树，在创建右子树
root.left = helper(in_left, index - 1);
root.right = helper(index + 1, in_right);
return root;
}
public TreeNode preorderAndInorderBuildTreeq2(int[] preorder, int[] inorder) {
// 边界判断
if (preorder.length == 0 || preorder == null) {
return null;
}
// 因为前序遍历数组第一个节点为根节点，所以先创建树的根节点
TreeNode root = new TreeNode(preorder[0]);
// 创建一个栈
Deque stack = new linkedList();
// 根节点入栈
stack.push(root);
// 创建一个变量表示中序数组的下标
int inorderIndex = 0;
for (int i = 1; i < preorder.length; i++) {
// 获取前序遍历数组当前的值
int preorderVal = preorder[i];
// 获取当前节点
TreeNode node = stack.peek();
// 判断当前节点的值与当前中序遍历数组的值是否相等
if (node.val != inorder[inorderIndex]) {
// 若不相等，则表明当前的 preorderVal 是当前节点的左儿子，那么将其创建并入栈
node.left = new TreeNode(preorderVal);
stack.push(root.left);
} else {
// 若不想等，则证明当前的 preorderVal 不是当前节点的左儿子了，那么 preorderVal 要么是当前节点的右儿子，要么是当前节点祖先的右儿子
// 寻找 preorderVal 的父节点
while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
// 向上回溯当前节点的祖先节点
node = stack.pop();
inorderIndex++;
}
node.right = new TreeNode(preorderVal);
stack.push(node.right);
}
}
return root;
}
public TreeNode preorderAndInorderBuildTreeq3(int[] preorder, int[] inorder) {
// 获取数组长度
int n = preorder.length - 1;
// 定义下标
int index = 0;
// 中序数组存入集合
for (Integer val : inorder) {
idx_map.put(val, index++);
}
return myBuildTree(preorder, inorder, 0, n, 0, n);
}
private TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
if (preorder_left > preorder_right) {
return null;
}
// 前序遍历数组的第一个节点就是根节点
int preorder_root_val = preorder[preorder_left];
// 创建根节点
TreeNode root = new TreeNode(preorder_root_val);
// 获取根节点在中序数组中的位置
int inorder_root_index = idx_map.get(preorder_root_val);
// 得到左子树的节点的数目
int size_left_subtree = inorder_root_index - inorder_left;
// 前序遍历左子树位置：[preorder_left+1, preorder_left+size_left_subtree] 对应中序中的左子树位置[inorder_left, inorder_root_index-1]
root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root_index - 1);
// 前序遍历右子树位置：[preorder_left+size_left_subtree+1, preorder_right 对应中序中的右子树位置[inorder_root_index+1, inorder_right]
root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root_index + 1, inorder_right);
return root;
}
}
2. 从中序与后序遍历序列构造二叉树
public class InorderAndPostorderBuildTree {
// 创建一些成员变量，方便调用
private int post_idx; // 表示树的根节点
private int[] inorder; // 中序遍历的数组
private int[] postorder; // 后序遍历的数组
private Map idx_map = new HashMap();
public TreeNode inorderAndPostorderBuildTree1(int[] inorder, int[] postorder) {
// 成员属性初始化
this.inorder = inorder;
this.postorder = postorder;
// 从后序遍历数组的最后一个元素开始
post_idx = postorder.length - 1;
// 定义一个idx表示中序数组的下标
int idx = 0;
// 将中序数组元素存入哈希表中
for (Integer val : inorder) {
idx_map.put(val, idx++);
}
return helper(0, inorder.length - 1);
}
private TreeNode helper(int in_left, int in_right) {
// in_left > in_right 说明子树为空，返回空
if (in_left > in_right) {
return null;
}
// 选择后序数组中 post_idx 的位置的元素作为当前子树的根节点
int root_val = postorder[post_idx];
TreeNode root = new TreeNode(root_val);
// 根据中序数组中 root 值所在的位置将数组分成两棵左右子树
int index = idx_map.get(root_val);
// 根节点下标减一
post_idx--;
// 构建右子树
root.right = helper(index + 1, in_right);
// 构建左子树
root.left = helper(in_left, index - 1);
return root;
}
public TreeNode inorderAndPostorderBuildTree2(int[] inorder, int[] postorder) {
// 边界处理
if (postorder.length == 0 || postorder == null) {
return null;
}
// 获取根节点
TreeNode root = new TreeNode(postorder[postorder.length - 1]);
// 创建一个栈
Deque stack = new linkedList();
// 根节点入栈
stack.push(root);
int inorderIndex = inorder.length - 1;
for (int i = postorder.length - 2; i >= 0; i--) {
// 获取当前后序数组遍历的值
int postorderVal = postorder[i];
// 获取当前头结点
TreeNode node = stack.peek();
if (node.val != inorder[inorderIndex]) {
node.right = new TreeNode(postorderVal);
stack.push(node.right);
} else {
while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
node = stack.pop();
inorderIndex--;
}
node.left = new TreeNode(postorderVal);
stack.push(node.left);
}
}
return root;
}
}
3. 填充每个节点的下一个右侧节点指针
public class ConnectRightNode {
public TreeNode connect1(TreeNode root) {
if (root == null) {
return null;
}
// 创建一个队列
Deque deque = new linkedList();
// 根节点入队
deque.add(root);
while (!deque.isEmpty()) {
// 得到每一层节点的个数
int size = deque.size();
// 一层出队，每个节点左右子节点入队。
for (int i = 0; i < size; i++) {
// 从队首取出元素
TreeNode node = deque.remove();
// 将每次出对的节点都连接起来
if (i < size - 1) {
node.next = deque.peek();
}
// 出队节点的左右子节点入队
if (node.left != null) {
deque.add(node.left);
}
if (node.right != null) {
deque.add(node.right);
}
}
}
return root;
}
public TreeNode connect2(TreeNode root) {
// 边界处理
if (root == null) {
return root;
}
// 从根节点开始，一层一层往下处理，leftmost作为第N-1层节点的头节点，再一个就是用来判断是否到达最后一层
TreeNode leftmost = root;
// 当到最后一层时，终止循环
while (leftmost.left != null) {
// 头结点复制一份，免得后面头节点的改变导致链表发生变化。
TreeNode head = leftmost;
while (head != null) {
// 同一个父节点
head.left.next = head.right;
// 不同父节点
if (head.next != null) {
head.right.next = head.next.left;
}
head = head.next;
}
leftmost = leftmost.left;
}
return root;
}
public TreeNode connect3(TreeNode root) {
dfs(root);
return root;
}
private void dfs(TreeNode root) {
if(root == null){
return;
}
TreeNode nodeLeft = root.left;
TreeNode nodeRight = root.right;
while (nodeLeft!= null){
nodeLeft.next = nodeRight;
nodeLeft = nodeLeft.right;
nodeRight = nodeRight.left;
}
dfs(root.left);
dfs(root.right);
}
}
4. 填充每个节点的下一个右侧节点指针 II
public class ConnectRightNodeTwo {
public TreeNode connect1(TreeNode root) {
if (root == null) {
return null;
}
// 创建一个队列
Deque deque = new linkedList();
// 根节点入队
deque.add(root);
while (!deque.isEmpty()) {
// 得到每一层节点的个数
int size = deque.size();
// 一层出队，每个节点左右子节点入队。
for (int i = 0; i < size; i++) {
// 从队首取出元素
TreeNode node = deque.remove();
// 将每次出对的节点都连接起来
if (i < size - 1) {
node.next = deque.peek();
}
// 出队节点的左右子节点入队
if (node.left != null) {
deque.add(node.left);
}
if (node.right != null) {
deque.add(node.right);
}
}
}
return root;
}
public TreeNode connect2(TreeNode root) {
if(root == null){
return root;
}
// 当前层的开始节点
TreeNode curNode = root;
while (curNode!=null){
// 创建下一层的头节点
TreeNode dummy = new TreeNode(0);
// 下一层的头结点复制一份，防止头节点发生改动。
TreeNode preNode = dummy;
// 开始遍历当前层的节点
while (curNode!=null){
// 当前层节点的左子树不为空，那么接到下一层链表的后面
if(curNode.left!=null){
preNode.next = curNode.left;
preNode = preNode.next;
}
// 当前层节点的右子树不为空，那么接到下一层链表的后面
if(curNode.right != null){
preNode.next = curNode.right;
preNode = preNode.next;
}
// 当前层节点后移一位
curNode = curNode.next;
}
// 将下一层的头节点的下一个节点作为当前层
curNode = dummy.next;
}
return root;
}
}
5. 二叉搜索树的最近公共祖先
public class LowestCommonAncestor {
public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
// 边界处理
if (root == null) {
return root;
}
// 得到从根节点到两个目标节点的路径
List path_P = getPath(root, p);
List path_Q = getPath(root, q);
// 定义祖先节点，初始化为根节点
TreeNode ancestonode = root;
// 遍历路径，找到祖先节点
for (int i = 0; i < path_P.size() && i < path_Q.size(); i++) {
if (path_P.get(i) == path_Q.get(i)) {
ancestonode = path_P.get(i);
} else {
break;
}
}
return ancestoNode;
}
private List getPath(TreeNode root, TreeNode target) {
List path = new ArrayList();
// 根节点复制一份，防止根节点在后面的操作中发生改变
TreeNode curNode = root;
while (curNode != target) {
// 列表先添加当前节点
path.add(curNode);
if (curNode.val > target.val) {
curNode = curNode.left;
} else {
curNode = curNode.right;
}
}
// 当前节点 == 目标节点时，加入列表
path.add(curNode);
return path;
}
public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
// 根节点复制一份
TreeNode curNode = root;
while (curNode != null) {
if (curNode.val > p.val && curNode.val > q.val) {
curNode = curNode.left;
} else if (curNode.val < p.val && curNode.val < q.val) {
curNode = curNode.right;
} else {
break;
}
}
return curNode;
}
public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode p, TreeNode q) {
if (root.val > p.val && root.val > q.val) {
return lowestCommonAncestor3(root.left, p, q);
}
if (root.val < p.val && root.val < q.val) {
return lowestCommonAncestor3(root.right, p, q);
}
return root;
}
}
6. 二叉树的最近公共祖先
public class BinaryTreeLowestCommonAncestor {
public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return root;
}
// 创捷一个哈希表来存储 <节点, 父节点>
Map parents = new HashMap();
// 根节点的父节点为 null
parents.put(root, null);
// 创建一个队列来 BFS
Deque deque = new linkedList();
// 根节点入队
deque.offer(root);
// 此时入队时不需要再用队列为空来作为终止条件了，只要当 parents 中包含 p、q 节点时，就可以中止了
while (!(parents.containsKey(p) && parents.containsKey(q))) {
TreeNode curNode = deque.poll();
if (curNode.left != null) {
// 子节点与父结点存入哈希表中
parents.put(curNode.left, curNode);
// 子节点入队
deque.offer(curNode.left);
}
if (curNode.right != null) {
parents.put(curNode.right, curNode);
deque.offer(curNode.right);
}
}
// 创建一个集合来存储根节点到 p 节点的路径
Set path = new HashSet();
// 循环将根节点到 p 节点经过的所有节点存入集合中
while (p != null) {
// 从 p 节点开始，并包含 p 节点，万一 p 节点是 q 节点的祖先呢！
path.add(p);
p = parents.get(p);
}
// 如果 q 节点的父节点在path中没有出现，那么就在向上找父节点，如果在path中出现，那么返回这个出现的节点
while (!path.contains(q)) {
q = parents.get(q);
}
return q;
}
public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
return null;
}
}
7. 序列化与反序列化二叉树
public class SeqToOppositeSeqBinaryTree {
// Encodes a tree to a single string.
public String serialize1(TreeNode root) {
if (root == null) {
return "None";
}
return root.val + "," + serialize1(root.left) + "," + serialize1(root.right);
}
// Decodes your encoded data to tree.
public TreeNode deserialize1(String data) {
// 将字符串切割成字符数组
String[] dataArray = data.split(",");
for (int i = 0; i < dataArray.length; i++) {
System.out.println(dataArray[i]);
}
// 将数组的元素放到队列里面去
List dataList = new linkedList<>(Arrays.asList(dataArray));
return buildTree(dataList);
}
private TreeNode buildTree(List dataList) {
if (dataList.get(0).equals("None")) {
dataList.remove(0);
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(dataList.get(0)));
dataList.remove(0);
root.left = buildTree(dataList);
root.right = buildTree(dataList);
return root;
}
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return "None";
}
String data = "";
// 创建一个队列
Deque deque = new linkedList();
// 根节点先入队
deque.offer(root);
while (!deque.isEmpty()) {
// 获取队首元素
TreeNode curNode = deque.poll();
if(curNode!=null){
data = data + Integer.valueOf(curNode.val).toString();
deque.add(curNode.left);
deque.add(curNode.right);
}else {
data = data + "None";
}
// 每次遍历一个节点都给后面加上一个','表间隔。
data = data + ",";
}
return data;
}
// Decodes your encoded data to tree.
public TreeNode deserialize3(String data) {
String[] dataArray = data.split(",");
List dataList = new linkedList(Arrays.asList(dataArray));
if (dataList.get(0).equals("None")) {
return null;
}
List listNode = new ArrayList();
// 创建根节点
TreeNode root = new TreeNode(Integer.valueOf(dataList.get(0)));
dataList.remove(0);
// 先把根节点放入链表中
listNode.add(root);
while (!dataList.isEmpty()) {
// 从listNode的第一个元素开始往后遍历
int listSize = listNode.size();
for (int i = 0; i < listSize; i++) {
TreeNode curNode = listNode.get(i);
if (!dataList.get(0).equals("None")) {
curNode.left = new TreeNode(Integer.valueOf(dataList.get(0)));
dataList.remove(0);
listNode.add(curNode.left);
} else {
curNode.left = null;
dataList.remove(0);
}
if (!dataList.get(0).equals("None")) {
curNode.right = new TreeNode(Integer.valueOf(dataList.get(0)));
dataList.remove(0);
listNode.add(curNode.right);
} else {
curNode.right = null;
dataList.remove(0);
}
}
}
return root;
}
public TreeNode deserialize4(String data) {
String[] dataArray = data.split(",");
if (dataArray[0].equals("None")) {
return null;
}
Deque deque = new linkedList();
// 创建根节点
TreeNode root = new TreeNode(Integer.valueOf(dataArray[0]));
deque.offer(root);
int i = 1;
while (!deque.isEmpty()) {
TreeNode curNode = deque.poll();
if (!dataArray[i].equals("None")) {
curNode.left = new TreeNode(Integer.valueOf(dataArray[i]));
deque.offer(curNode.left);
}
i++;
if (!dataArray[i].equals("None")) {
curNode.right = new TreeNode(Integer.valueOf(dataArray[i]));
deque.offer(curNode.right);
}
i++;
}
return root;
}
}
Deque.offer()：将指定元素插入此双端队列表示的队列中（换句话说，在此双端队列的尾部）。Deque.poll()：检索并删除此双端队列表示的队列的头部（换句话说，此双端队列的第一个元素)，如果此双端队列为空，则返回null
