[TOC]
68. 树中两个节点的最低公共祖先
68.1 二叉查找树
在二叉查找树中，两个节点 p, q 的公共祖先 root 满足 root.val >= p.val && root.val <= q.val。
image.png
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null)
return root;
if (root.val > p.val && root.val > q.val)
return lowestCommonAncestor(root.left, p, q);
if (root.val < p.val && root.val < q.val)
return lowestCommonAncestor(root.right, p, q);
return root;
}
68.2 普通二叉树
解题思路
在左右子树中查找是否存在 p 或者 q，如果 p 和 q 分别在两个子树中，那么就说明根节点就是最低公共祖先。
image.png
2，递归写法
public TreeNode lowestCommonAncestor(TreeNode cur, TreeNode p, TreeNode q) {
if (cur == null || cur == p || cur == q)
return cur;
TreeNode left = lowestCommonAncestor(cur.left, p, q);
TreeNode right = lowestCommonAncestor(cur.right, p, q);
//如果left为空，说明这两个节点在cur结点的右子树上，我们只需要返回右子树查找的结果即可
if (left == null)
return right;
//同上
if (right == null)
return left;
//如果left和right都不为空，说明这两个节点一个在cur的左子树上一个在cur的右子树上，
//我们只需要返回cur结点即可。
return cur;
}
不是很好理解
递归解法
要想找到两个节点的最近公共祖先节点，我们可以从两个节点往上找，每个节点都往上走，一直走到根节点，那么根节点到这两个节点的连线肯定有相交的地方，如果是从上往下走，那么最后一次相交的节点就是他们的最近公共祖先节点。我们就以找6和7的最近公共节点来画个图看一下
image.png
我们看到6和7公共祖先有5和3，但最近的是5。我们只要往上找，找到他们第一个相同的公共祖先节点即可，但怎么找到每个节点的父节点呢，我们只需要把每个节点都遍历一遍，然后顺便记录他们的父节点存储在Map中。我们先找到其中的一条路径，比如6→5→3，然后在另一个节点往上找，由于7不在那条路径上，我们找7的父节点是2，2也不在那条路径上，我们接着往上找，2的父节点是5，5在那条路径上，所以5就是他们的最近公共子节点。
其实这里我们可以优化一下，我们没必要遍历所有的结点，我们一层一层的遍历（也就是BFS），只需要这两个节点都遍历到就可以了，比如上面2和8的公共结点，我们只需要遍历到第3层，把2和8都遍历到就行了，没必要再遍历第4层了。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//记录遍历到的每个节点的父节点。
Map<TreeNode, TreeNode> parent = new HashMap<>();
Queue<TreeNode> queue = new LinkedList<>();
parent.put(root, null);//根节点没有父节点，所以为空
queue.add(root);
//直到两个节点都找到为止。
while (!parent.containsKey(p) || !parent.containsKey(q)) {
//队列是一边进一边出，这里poll方法是出队，
TreeNode node = queue.poll();
if (node.left != null) {
//左子节点不为空，记录下他的父节点
parent.put(node.left, node);
//左子节点不为空，把它加入到队列中
queue.add(node.left);
}
//右节点同上
if (node.right != null) {
parent.put(node.right, node);
queue.add(node.right);
}
}
Set<TreeNode> ancestors = new HashSet<>();
//记录下p和他的祖先节点，从p节点开始一直到根节点。
while (p != null) {
ancestors.add(p);
p = parent.get(p);
}
//查看p和他的祖先节点是否包含q节点，如果不包含再看是否包含q的父节点……
while (!ancestors.contains(q))
q = parent.get(q);
return q;
}
退化成链表的公共祖先思路
class Solution {
public:
void getPath(TreeNode *root, TreeNode *end, vector<TreeNode*>& path) {
stack<TreeNode*> stk;
TreeNode *p = root, *prev = nullptr;
while (p || !stk.empty()) {
while (p) {
stk.push(p);
path.push_back(p);
if (p == end) return;
p = p->left;
}
p = stk.top();
if (!p->right || p->right == prev) {
path.pop_back();
stk.pop();
prev = p;
p = nullptr;
} else {
p = p->right;
}
}
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> path1, path2;
getPath(root, p, path1);
getPath(root, q, path2);
int n = min(path1.size(), path2.size());
TreeNode *last = nullptr;
for (int i = 0; i < n; i++) {
if (path1[i] != path2[i]) return last;
last = path1[i];
}
return last;
}
};
看着只能是后续遍历？
是的，
需要判断是否访问过了，因为一个节点可能多次从stack中pop。
55.1 二叉树的深度
从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
image.png
public int TreeDepth(TreeNode root) {
return root == null ? 0 : 1 + Math.max(TreeDepth(root.left), TreeDepth(root.right));
}
非递归：
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.*;
public class Solution {
public int TreeDepth(TreeNode root) {
LinkedList <TreeNode> list = new LinkedList<TreeNode>();
if(root == null){
return 0;
}
int level = 0;
list.add(root);
while(!list.isEmpty()){
//记录当前层的节点个数
int curSize = list.size();
while(curSize>0){
TreeNode curNode = list.poll();
if(curNode.left!=null){
list.add(curNode.left);
}
if(curNode.right!=null){
list.add(curNode.right);
}
curSize--;
}
level++;
}
return level;
}
}
55.2 平衡二叉树
平衡二叉树左右子树高度差不超过 1。
image.png
private boolean isBalanced = true;
public boolean IsBalanced_Solution(TreeNode root) {
height(root);
return isBalanced;
}
private int height(TreeNode root) {
if (root == null || !isBalanced)
return 0;
int left = height(root.left);
int right = height(root.right);
if (Math.abs(left - right) > 1)
isBalanced = false;
return 1 + Math.max(left, right);
}
上述做法的缺点是，当在某个子树不满足条件，被判断不是平衡二叉树后，还会进行很多次计算，直到计算到根节点的最大深度为止。这是因为上面的做法需要遍历所有的节点。因此使用剪枝。
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
return getDepth(root) != -1;
}
private int getDepth(TreeNode root) {
if (root == null) return 0;
int left = getDepth(root.left);
if (left == -1) return -1;
int right = getDepth(root.right);
if (right == -1) return -1;
return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
}
}
根据大佬的思路，将思路1的写法进行剪枝。其实就是多加两个判断，不符合条件的，直接一直向上返回，没必要还去计算深度。
二叉树中和为某一值的路径
输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
下图的二叉树有两条和为 22 的路径：10, 5, 7 和 10, 12
image.png
前序遍历
非递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()) {
root = stack.pop();
list.add(root.val);
if (root.right != null) {
stack.push(root.right);
}
if (root.left != null) {
stack.push(root.left);
}
}
return list;
}
}
中序遍历
递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
inorderTraversal(root, list);
return list;
}
private void inorderTraversal(TreeNode node, List<Integer> list) {
if (node == null) {
return;
}
inorderTraversal(node.left, list);
list.add(node.val);
inorderTraversal(node.right, list);
}
}
非递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || root != null) {
while(root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
list.add(root.val);
root = root.right;
}
return list;
}
}
树的深度
非递归 层次遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int maxDepth(TreeNode root) {
if(root==null) return 0;
Queue<TreeNode> queue =new LinkedList<>();
queue.offer(root);
int count=0;
while(!queue.isEmpty()){
int size = queue.size();
while(size-->0){
TreeNode curr =queue.poll();
if(curr.left!=null) queue.offer(curr.left);
if(curr.right!=null) queue.offer(curr.right);
}
count++;
}
return count;
}
}
递归
public class Solution {
public int minDepth(TreeNode root) {
if(root == null) return 0;
int left = minDepth(root.left);
int right = minDepth(root.right);
return (left == 0 || right == 0) ? left + right + 1: Math.min(left,right) + 1;
}
}
112. Path Sum
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if(root==null) return false;
if(root.left==null&&root.right==null) return root.val==sum;
return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right, sum-root.val);
}
}
path sum并打印路径
非递归 设计到后序遍历
public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
Stack<TreeNode> stack = new Stack<TreeNode>();
int SUM = 0;
TreeNode cur = root;
TreeNode pre = null;
while(cur!=null || !stack.isEmpty()){
while(cur!=null){
stack.push(cur);
path.add(cur.val);
SUM+=cur.val;
cur=cur.left;
}
cur = stack.peek();
if(cur.right!=null && cur.right!=pre){
cur = cur.right;
continue;
}
if(cur.left==null && cur.right==null && SUM==sum)
res.add(new ArrayList<Integer>(path));
pre = cur;
stack.pop();
path.remove(path.size()-1);
SUM-=cur.val;
cur = null;
}
return res;
}
}
回溯法
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> ret =new ArrayList<>();
backTrack(ret,root,new ArrayList<TreeNode>(),sum);
return ret;
}
public void backTrack(List ret, TreeNode root, List list, int sum){
if(root==null) return;
list.add(root.val);
if(root.left==null &&root.right==null && sum==root.val){
ret.add(new ArrayList(list));
}
else{
backTrack(ret,root.left,list,sum-root.val);
backTrack(ret,root.right,list,sum-root.val);
}
list.remove(list.size()-1);
}
}
Binary Tree Maximum Path Sum
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int maxPathSum(TreeNode root) {
if(root==null) return 0;
int[] ret=new int[1];
ret[0]=Integer.MIN_VALUE;
maxSum(root,ret);
return ret[0];
}
public int maxSum(TreeNode root, int[] ret){
if(root==null) return 0;
int left=Math.max(0,maxSum(root.left,ret));
int right=Math.max(0,maxSum(root.right, ret));
ret[0]=Math.max(ret[0], left+right+root.val);
return Math.max(left, right)+root.val;
}
}
二叉树宽度
Given the root of a binary tree, return the maximum width of the given tree.
The maximum width of a tree is the maximum width among all levels.
The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes are also counted into the length calculation.
class Solution {
public int widthOfBinaryTree(TreeNode root) {
if(root == null) return 0;
Deque<TreeNode> queue = new ArrayDeque<>();
//使用节点的值来记录节点在二叉树上的位置
root.val = 0;
queue.add(root);
int res = Integer.MIN_VALUE;
while(!queue.isEmpty()){
int n = queue.size();
//队列结尾减去开头的值加一即为当前层的宽度
res = Math.max(res,queue.getLast().val - queue.getFirst().val + 1);
for(int i = 0;i < n;i++){
TreeNode node = queue.poll();
if(node.left != null){
node.left.val = node.val*2;
queue.add(node.left);
}
if(node.right != null){
node.right.val = node.val*2 + 1;
queue.add(node.right);
}
}
}
return res;
}
}
作者：lan-ch
链接：https://leetcode-cn.com/problems/maximum-width-of-binary-tree/solution/662-er-cha-shu-zui-da-kuan-du-by-lan-ch-tjyz/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
Using your solution and not changing the tree value
public int widthOfBinaryTree(TreeNode root) {
if (root == null) {
return 0;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);
LinkedList<Integer> q = new LinkedList();
q.offer(1);
int max = 1;
while (!queue.isEmpty()) {
int size = queue.size();
max = Math.max(max, q.peekLast() - q.peekFirst() + 1);
for (int i = 0; i < size; i++) {
root = queue.poll();
int temp=q.poll();
if (root.left != null) {
queue.offer(root.left);
q.offer(2*temp);
}
if (root.right != null) {
queue.offer(root.right);
q.offer(2*temp+1);
}
}
}
return max;
}
