算法之美——二叉树
作者: 康凯森
日期: 2016-11-19
分类: 算法
解题思路
碰到二叉树的问题,就想想整棵树在该问题上的结果和左右儿子在该问题上的结果之间的联系是什么。
Traverse vs Divide Conquer
- 都是递归算法
- 结果在参数中 vs 结果在返回值中
- 自顶向下 vs 自底向上
二叉树前序遍历
非递归
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Preorder in ArrayList which contains node values.
*/
public ArrayList<Integer> preorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
ArrayList<Integer> preorder = new ArrayList<Integer>();
if (root == null) {
return preorder;
}
stack.push(root);
while (!stack.empty()) {
TreeNode node = stack.pop();
preorder.add(node.val);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return preorder;
}
}
Traverse
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<Integer>();
traverse(root, result);
return result;
}
// 把root为根的preorder加入result里面
private void traverse(TreeNode root, ArrayList<Integer> result) {
if (root == null) {
return;
}
result.add(root.val);
traverse(root.left, result);
traverse(root.right, result);
}
}
Divide & Conquer
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<Integer>();
// null or leaf
if (root == null) {
return result;
}
// Divide
ArrayList<Integer> left = preorderTraversal(root.left);
ArrayList<Integer> right = preorderTraversal(root.right);
// Conquer
result.add(root.val);
result.addAll(left);
result.addAll(right);
return result;
}
}
二叉树中序遍历
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Inorder in ArrayList which contains node values.
*/
public ArrayList<Integer> inorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
ArrayList<Integer> result = new ArrayList<Integer>();
TreeNode curt = root;
while (curt != null || !stack.empty()) {
while (curt != null) {
stack.push(curt);
curt = curt.left;
}
curt = stack.pop();
result.add(curt.val);
curt = curt.right;
}
return result;
}
}
二叉树后序遍历
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Postorder in ArrayList which contains node values.
*/
public ArrayList<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
ArrayList<Integer> result = new ArrayList<Integer>();
if (root == null){
return result;
}
TreeNode curt = root;
TreeNode prev = null;
stack.push(root);
while (!stack.empty()) {
curt = stack.peek();
if ((curt.left == null && curt.right == null) ||
(prev != null &&(prev == curt.left || prev == curt.right))){
result.add(curt.val);
stack.pop();
prev = curt;
}
else{
if(curt.right != null){
stack.push(curt.right);
}
if(curt.left != null){
stack.push(curt.left);
}
}
}
return result;
}
}
二叉树的最大深度
public class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left, right) + 1;
}
}
Traverse
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: The root of binary tree.
* @return: An integer.
*/
private int depth;
public int maxDepth(TreeNode root) {
depth = 0;
helper(root, 1);
return depth;
}
private void helper(TreeNode node, int curtDepth) {
if (node == null) {
return;
}
if (curtDepth > depth) {
depth = curtDepth;
}
helper(node.left, curtDepth + 1);
helper(node.right, curtDepth + 1);
}
}
二叉树的最小深度
public class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
return getMin(root);
}
public int getMin(TreeNode root){
if (root == null) {
return Integer.MAX_VALUE;
}
if (root.left == null && root.right == null) {
return 1;
}
return Math.min(getMin(root.left), getMin(root.right)) + 1;
}
}
平衡二叉树判断
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: The root of binary tree.
* @return: True if this Binary tree is Balanced, or false.
*/
public boolean isBalanced(TreeNode root) {
return maxDepth(root) != -1;
}
private int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
if (left == -1 || right == -1 || Math.abs(left-right) > 1) {
return -1;
}
return Math.max(left, right) + 1;
}
}
最近公共祖先
// 有父指针时 可以转化为寻找俩个链表的第一个公共节点
//Divide & Conquer
public class Solution {
// 在root为根的二叉树中找A,B的LCA:
// 如果找到了就返回这个LCA
// 如果只碰到A，就返回A
// 如果只碰到B，就返回B
// 如果都没有，就返回null
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
if (root == null || root == node1 || root == node2) {
return root;
}
// Divide
TreeNode left = lowestCommonAncestor(root.left, node1, node2);
TreeNode right = lowestCommonAncestor(root.right, node1, node2);
// Conquer
if (left != null && right != null) {
return root;
}
if (left != null) {
return left;
}
if (right != null) {
return right;
}
return null;
}
}
最近公共祖先2
public class Solution {
/**
* @param root: The root of the tree
* @param A, B: Two node in the tree
* @return: The lowest common ancestor of A and B
*/
public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root,
ParentTreeNode A,
ParentTreeNode B) {
// Write your code here
if (root == null || root == A || root == B) {
return root;
}
int lengthA = getLength (A);
int lengthB = getLength (B);
int diff = lengthA - lengthB;
ParentTreeNode tempA = null;
ParentTreeNode tempB = null;
if (diff >= 0) {
tempA = skip (A, diff);
tempB = B;
} else {
tempB = skip (B, -diff);
tempA = A;
}
while (tempA != null && tempB != null && tempA != tempB) {
tempA = tempA.parent;
tempB = tempB.parent;
}
return tempA;
}
private int getLength (ParentTreeNode A) {
int length = 0;
ParentTreeNode temp = A;
while(temp != null) {
length ++;
temp = temp.parent;
}
return length;
}
private ParentTreeNode skip (ParentTreeNode A, int diff) {
ParentTreeNode temp = A;
for (int i = 0; i < diff; i++) {
temp = temp.parent;
}
return temp;
}
}
二叉树中的最大路径和
//any to any VS root to any
public class Solution {
private class ResultType {
// singlePath: 从root往下走到任意点的最大路径，这条路径可以不包含任何点
// maxPath: 从树中任意到任意点的最大路径，这条路径至少包含一个点（也就是root）
int singlePath, maxPath;
ResultType(int singlePath, int maxPath) {
this.singlePath = singlePath;
this.maxPath = maxPath;
}
}
private ResultType helper(TreeNode root) {
if (root == null) {
return new ResultType(0, Integer.MIN_VALUE);
}
// Divide
ResultType left = helper(root.left);
ResultType right = helper(root.right);
// Conquer
int singlePath = Math.max(left.singlePath, right.singlePath) + root.val;
singlePath = Math.max(singlePath, 0);
int maxPath = Math.max(left.maxPath, right.maxPath);
maxPath = Math.max(maxPath, left.singlePath + right.singlePath + root.val);
return new ResultType(singlePath, maxPath);
}
public int maxPathSum(TreeNode root) {
ResultType result = helper(root);
return result.maxPath;
}
}
二叉树的最大路径和 II
上一题的简化版
public class Solution {
/**
* @param root the root of binary tree.
* @return an integer
*/
public int maxPathSum2(TreeNode root) {
// Write your code here
if (root == null) {
return 0;
}
// Divide
int left = maxPathSum2(root.left);
int right = maxPathSum2(root.right);
// Conquer
int maxPath = Math.max(left, right) + root.val;
return maxPath;
}
}
二叉树的层次遍历
// version 1: BFS
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Level order a list of lists of integer
*/
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
// write your code here
ArrayList<ArrayList<Integer>> results= new ArrayList<ArrayList<Integer>>();
if (root == null)
return results;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
ArrayList<Integer> result = new ArrayList<Integer>();
int size = queue.size();
for (int i = 0; i < size; i++){
TreeNode temp = queue.poll();
result.add(temp.val);
if (temp.left != null)
queue.offer(temp.left);
if (temp.right != null)
queue.offer(temp.right);
}
results.add(result);
}
return results;
}
}
// version 2: DFS
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Level order a list of lists of integer
*/
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
if (root == null) {
return results;
}
int maxLevel = 0;
while (true) {
ArrayList<Integer> level = new ArrayList<Integer>();
dfs(root, level, 0, maxLevel);
if (level.size() == 0) {
break;
}
results.add(level);
maxLevel++;
}
return results;
}
private void dfs(TreeNode root,
ArrayList<Integer> level,
int curtLevel,
int maxLevel) {
if (root == null || curtLevel > maxLevel) {
return;
}
if (curtLevel == maxLevel) {
level.add(root.val);
return;
}
dfs(root.left, level, curtLevel + 1, maxLevel);
dfs(root.right, level, curtLevel + 1, maxLevel);
}
}
// version 3: BFS. two queues
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Level order a list of lists of integer
*/
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (root == null) {
return result;
}
ArrayList<TreeNode> Q1 = new ArrayList<TreeNode>();
ArrayList<TreeNode> Q2 = new ArrayList<TreeNode>();
Q1.add(root);
while (Q1.size() != 0) {
ArrayList<Integer> level = new ArrayList<Integer>();
Q2.clear();
for (int i = 0; i < Q1.size(); i++) {
TreeNode node = Q1.get(i);
level.add(node.val);
if (node.left != null) {
Q2.add(node.left);
}
if (node.right != null) {
Q2.add(node.right);
}
}
// swap q1 and q2
ArrayList<TreeNode> temp = Q1;
Q1 = Q2;
Q2 = temp;
// add to result
result.add(level);
}
return result;
}
}
// version 4: BFS, queue with dummy node
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Level order a list of lists of integer
*/
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (root == null) {
return result;
}
Queue<TreeNode> Q = new LinkedList<TreeNode>();
Q.offer(root);
Q.offer(null); // dummy node
ArrayList<Integer> level = new ArrayList<Integer>();
while (!Q.isEmpty()) {
TreeNode node = Q.poll();
if (node == null) {
if (level.size() == 0) {
break;
}
result.add(level);
level = new ArrayList<Integer>();
Q.offer(null); // add a new dummy node
continue;
}
level.add(node.val);
if (node.left != null) {
Q.offer(node.left);
}
if (node.right != null) {
Q.offer(node.right);
}
}
return result;
}
}
二叉树倒序层次遍历
// 借助二叉树层次遍历结果，逆序
或者 利用 add(int index, E element) API.
public class Solution {
/**
* @param root: The root of binary tree.
* @return: buttom-up level order a list of lists of integer
*/
public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
// write your code here
ArrayList<ArrayList<Integer>> results= new ArrayList<ArrayList<Integer>>();
if (root == null)
return results;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
ArrayList<Integer> result = new ArrayList<Integer>();
int size = queue.size();
for (int i = 0; i < size; i++){
TreeNode temp = queue.poll();
result.add(temp.val);
if (temp.left != null)
queue.offer(temp.left);
if (temp.right != null)
queue.offer(temp.right);
}
results.add(0, result);
}
return results;
}
}
###二叉树的锯齿形层次遍历
public class Solution {
/**
* @param root: The root of binary tree.
* @return: A list of lists of integer include
* the zigzag level order traversal of its nodes' values
*/
public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
// write your code here
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (root == null) {
return result;
}
Stack<TreeNode> currLevel = new Stack<TreeNode>();
Stack<TreeNode> nextLevel = new Stack<TreeNode>();
Stack<TreeNode> tmp;
currLevel.push(root);
boolean normalOrder = true;
while (!currLevel.isEmpty()) {
ArrayList<Integer> currLevelResult = new ArrayList<Integer>();
while (!currLevel.isEmpty()) {
TreeNode node = currLevel.pop();
currLevelResult.add(node.val);
if (normalOrder) {
if (node.left != null) {
nextLevel.push(node.left);
}
if (node.right != null) {
nextLevel.push(node.right);
}
} else {
if (node.right != null) {
nextLevel.push(node.right);
}
if (node.left != null) {
nextLevel.push(node.left);
}
}
}
result.add(currLevelResult);
tmp = currLevel;
currLevel = nextLevel;
nextLevel = tmp;
normalOrder = !normalOrder;
}
return result;
}
}
验证二叉查找树
public class Solution {
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean dfs(TreeNode root, long low, long up) {
if (root == null) {
return true;
}
if (root.val >= up || root.val <= low) {
return false;
}
return dfs(root.left, low, root.val) && dfs(root.right, root.val, up);
}
}
二叉搜索树查找中序后继
1. 这个BST是否有parent指针：如果有，则直接用父指针往上找。如果没有，则从root开始往下找。
2. 要查找的点是否有右孩子：如果有，简单，直接找右子树的最小节点。如果没有，则找到比该节点大且相差最小的父节点。
时间复杂度都是O(h), h是树高。
public class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
TreeNode successor = null;
while (root != null && root.val != p.val) {
if (root.val > p.val) {
successor = root;
root = root.left;
} else {
root = root.right;
}
}
if (root == null) {
return null;
}
if (root.right == null) {
return successor;
}
root = root.right;
while (root.left != null) {
root = root.left;
}
return root;
}
}
二叉搜索树的迭代
// 就是中序遍历
public class BSTIterator {
//@param root: The root of binary tree.
Stack<TreeNode> treeStack = new Stack<TreeNode>();
TreeNode current;
public BSTIterator(TreeNode root) {
// write your code here
while(!treeStack.isEmpty()){
treeStack.pop();
}
current = root;
}
//@return: True if there has next node, or false
public boolean hasNext() {
// write your code here
return (current != null || !treeStack.isEmpty());
}
//@return: return next node
public TreeNode next() {
// write your code here
while (current != null){
treeStack.push(current);
current = current.left;
}
current = treeStack.pop();
TreeNode temp = current;
current = current.right;
return temp;
}
}
二叉查找树的搜索区间
public class Solution {
private ArrayList<Integer> results;
/**
* @param root: The root of the binary search tree.
* @param k1 and k2: range k1 to k2.
* @return: Return all keys that k1<=key<=k2 in increasing order.
*/
public ArrayList<Integer> searchRange(TreeNode root, int k1, int k2) {
results = new ArrayList<Integer>();
helper(root, k1, k2);
return results;
}
private void helper(TreeNode root, int k1, int k2) {
if (root == null) {
return;
}
if (root.val > k1) {
helper(root.left, k1, k2);
}
if (root.val >= k1 && root.val <= k2) {
results.add(root.val);
}
if (root.val < k2) {
helper(root.right, k1, k2);
}
}
}
在二叉查找树中插入节点
public class Solution {
/**
* @param root: The root of the binary search tree.
* @param node: insert this node into the binary search tree
* @return: The root of the new binary search tree.
*/
public TreeNode insertNode(TreeNode root, TreeNode node) {
if (root == null){
return node;
}
if (node.val <= root.val) {
if (root.left == null)
root.left = node;
else
insertNode(root.left,node);
}
else {
if (root.right == null)
root.right = node;
else
insertNode(root.right,node);
}
return root;
}
}
删除二叉查找树的节点 再思考
public class Solution {
/**
* @param root: The root of the binary search tree.
* @param value: Remove the node with given value.
* @return: The root of the binary search tree after removal.
*/
public TreeNode removeNode(TreeNode root, int value) {
if (root==null) return null;
TreeNode preRoot = new TreeNode(0);
preRoot.left = root;
searchNodeRecur(preRoot,root,value);
return preRoot.left;
}
public void searchNodeRecur(TreeNode pre, TreeNode cur, int val){
//if there is no such node, then do nothing.
if (cur==null) return;
//find the node.
if (cur.val == val){
removeNode(pre,cur);
return;
} else if (cur.val > val){
searchNodeRecur(cur,cur.left,val);
} else
searchNodeRecur(cur,cur.right,val);
}
public void removeNode(TreeNode pre, TreeNode cur){
//a leaf node.
if (cur.left==null && cur.right==null){
if (pre.left==cur){
pre.left = null;
}
else{
pre.right = null;
}
}
else if (cur.left==null || cur.right==null){ //cur only has one sub tre
TreeNode child = (cur.left==null) ? cur.right : cur.left;
if (pre.left==cur) pre.left = child;
else pre.right=child;
}
else { //has two sub trees, select the largest node in the left subtree
TreeNode pre2 = cur;
TreeNode cur2 = cur.left;
while (cur2.right!=null){
pre2 = cur2;
cur2 = cur2.right;
}
//a leaf node
if (cur2.left==null){
if (pre2.left==cur2) pre2.left = null;
else pre2.right=null;
cur2.left = cur.left;
cur2.right = cur.right;
if (pre.left==cur) pre.left=cur2;
else pre.right=cur2;
} else {
if (pre2.left==cur2) pre2.left = cur2.left;
else pre2.right = cur2.left;
cur2.left = cur.left;
cur2.right = cur.right;
if (pre.left==cur) pre.left=cur2;
else pre.right=cur2;
}
}
}
}
二叉树的路径和
public class Solution {
/**
* @param root the root of binary tree
* @param target an integer
* @return all valid paths
*/
public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
// Write your code here
List<List<Integer>> results = new ArrayList ();
List <Integer> result = new ArrayList<Integer> ();
int sum = 0;
if (root == null){
return results;
}
helper(root, sum, target, result, results);
return results;
}
private void helper(TreeNode root, int sum, int target, List<Integer> result,
List<List<Integer>> results) {
sum += root.val;
result.add(root.val);
if (sum == target && root.left == null && root.right == null) {
results.add(new ArrayList<Integer>(result));
return;
}
if (root.left != null) {
helper(root.left, sum, target, result, results);
result.remove(result.size()-1);
}
if (root.right != null) {
helper(root.right, sum, target, result, results);
result.remove(result.size()-1);
}
}
}
扭转后等价的二叉树
public class Solution {
/**
* @param a, b, the root of binary trees.
* @return true if they are tweaked identical, or false.
*/
public boolean isTweakedIdentical(TreeNode a, TreeNode b) {
// Write your code here
// if (a == null && b!= null || a != null && b == null){
// return false;
// }
if (a == null && b == null) {
return true;
}
if (a == null || b == null) {
return false;
}
if (a.val != b.val) {
return false;
}
if (isTweakedIdentical(a.left, b.left) && isTweakedIdentical(a.right, b.right)) {
return true;
}
if (isTweakedIdentical(a.left, b.right) && isTweakedIdentical(a.right, b.left)) {
return true;
}
return false;
}
}
等价二叉树
public class Solution {
/**
* @param a, b, the root of binary trees.
* @return true if they are identical, or false.
*/
public boolean isIdentical(TreeNode a, TreeNode b) {
// Write your code here
if (a == null && b == null) {
return true;
}
if (a == null || b == null) {
return false;
}
if (a.val != b.val) {
return false;
}
if (isIdentical(a.left, b.left) && isIdentical(a.right, b.right)) {
return true;
}
return false;
}
}
对称二叉树
public class Solution {
/**
* @param root, the root of binary tree.
* @return true if it is a mirror of itself, or false.
*/
public boolean isSymmetric(TreeNode root) {
// Write your code here
if (root == null) {
return true;
}
return check(root.left, root.right);
}
private boolean check(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 == null) {
return true;
}
if (root1 == null || root2 == null) {
return false;
}
if (root1.val != root2.val) {
return false;
}
return check(root1.left, root2.right) && check(root1.right, root2.left);
}
}
完全二叉树
class ResultType {
public int depth;
public boolean isFull, isComplete;
ResultType(int depth, boolean isFull, boolean isComplete) {
this.depth = depth;
this.isFull = isFull;
this.isComplete = isComplete;
}
}
public class Solution {
/**
* @param root, the root of binary tree.
* @return true if it is a complete binary tree, or false.
*/
public boolean isComplete(TreeNode root) {
ResultType result = helper(root);
return result.isComplete;
}
private ResultType helper(TreeNode root) {
if (root == null) {
return new ResultType(0, true, true);
}
ResultType left = helper(root.left);
ResultType right = helper(root.right);
if (!left.isComplete) {
return new ResultType(-1, false, false);
}
// depth is the same, left should be full and right should be complete
if (left.depth == right.depth) {
if (!left.isFull || !right.isComplete) {
return new ResultType(-1, false, false);
}
return new ResultType(left.depth + 1, right.isFull, true);
}
// left.depth = right.depth + 1, left should be full and right should be full
if (left.depth == right.depth + 1) {
if (!left.isComplete || !right.isFull) {
return new ResultType(-1, false, false);
}
return new ResultType(left.depth + 1, false, true);
}
return new ResultType(-1, false, false);
}
}
参考资料
《OLAP 性能优化指南》欢迎 Star&共建
欢迎关注微信公众号
