需要熟练的树算法题
1、重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
>前序遍历 preorder = [3,9,20,15,7] >中序遍历 inorder = [9,3,15,20,7] >返回： 3 / \ 9 20 / \ 15 7
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
int n = preorder.length;
if (n == 0)
return null;
int rootVal = preorder[0], rootIndex = 0;
// 找中序根的索引
for (int i = 0; i < n; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
TreeNode root = new TreeNode(rootVal);
// 注意边界
// left
root.left = buildTree(
Arrays.copyOfRange(preorder, 1, 1 + rootIndex),
Arrays.copyOfRange(inorder, 0, rootIndex));
// right
root.right = buildTree(
Arrays.copyOfRange(preorder, 1 + rootIndex, n),
Arrays.copyOfRange(inorder, 1 + rootIndex, n));
return root;
}
}2、二叉树的下一个结点
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
// 中序
public class T57 {
public TreeLinkNode GetNext(TreeLinkNode pNode) {
if (null == pNode) {
return null;
}
// 两种情况
if (null != pNode.right) {
TreeLinkNode node = pNode.right;
while (null != node.left) {
node = node.left;
}
return node;
}
while (null != pNode.next) {
TreeLinkNode parent = pNode.next;
if (parent.left == pNode) {
return parent;
}
pNode = pNode.next;
}
return null;
}
}3、树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
>给定的树 A: 3 / \ 4 5 / \ 1 2 >给定的树 B： 4 / 1 >返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。>输入：A = [1,2,3], B = [3,1] >输出：false>输入：A = [3,4,5,1,2], B = [4,1] >输出：true
public class T17 {
public boolean HasSubtree(TreeNode root1, TreeNode root2) {
if (root1 == null || root2 == null)
return false;
return isSubtreeWithRoot(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
}
private boolean isSubtreeWithRoot(TreeNode root1, TreeNode root2) {
if (root2 == null)
return true;
if (root1 == null)
return false;
if (root1.val != root2.val)
return false;
return isSubtreeWithRoot(root1.left, root2.left) && isSubtreeWithRoot(root1.right, root2.right);
}
}3、二叉树的镜像
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
>例如输入： 4 / \ 2 7 / \ / \ >1 3 6 9 >镜像输出： 4 / \ 7 2 / \ / \ >9 6 3 1>输入：root = [4,2,7,1,3,6,9] >输出：[4,7,2,9,6,3,1]
public class T18 {
public void Mirror(TreeNode root) {
// 判断
if (root == null) return;
swap(root);
Mirror(root.left);
Mirror(root.right);
}
private void swap(TreeNode root) {
TreeNode t = root.left;
root.left = root.right;
root.right = t;
}
}
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if (root == null) return null;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
TreeNode cur;
while (!queue.isEmpty()) {
cur = queue.poll();
if(cur.left != null) queue.add(cur.left);
if (cur.right != null) queue.add(cur.right);
swap(cur);
}
return root;
}
private void swap(TreeNode root) {
TreeNode t = root.left;
root.left = root.right;
root.right = t;
}
}4、对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
>例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 1 / \ 2 2 / \ / \ >3 4 4 3 >但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 1 / \ 2 2 \ \ 3 3>输入：root = [1,2,2,3,4,4,3] >输出：true>输入：root = [1,2,2,null,3,null,3] >输出：false
public class T58 {
boolean isSymmetrical(TreeNode pRoot) {
if (null == pRoot) {
return true;
}
return comRoot(pRoot.left, pRoot.right);
}
private boolean comRoot(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null || right == null) {
return false;
}
if (left.val != right.val) {
return false;
}
// 左右对比
return comRoot(left.right, right.left) && comRoot(left.left, right.right);
}
}5.1、从上往下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
>如: >给定二叉树: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 >返回： >[3,9,20,15,7]
public class T22 {
// 层序遍历
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
// 需要用到队列
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root); // 第一次先加根入队
while (!queue.isEmpty()) {
int cnt = queue.size();
// 如果队列不为空的话， 队列出一个元素
while(cnt-- > 0) {
TreeNode t = queue.poll();
if (t == null) continue;
list.add(t.val);
queue.add(t.left);
queue.add(t.right);
}
}
return list;
}
}5.2、把二叉树打印多行
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
>输入 >{8,6,10,5,7,9,11} >返回值 >[[8],[6,10],[5,7,9,11]]
public class T60 {
ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(pRoot);
while (!queue.isEmpty()) {
ArrayList<Integer> list = new ArrayList<>();
int cnt = queue.size();
while (cnt-- > 0) {
TreeNode node = queue.poll();
if (node == null) continue;
list.add(node.val);
queue.add(node.left);
queue.add(node.right);
}
if (list.size() != 0) ret.add(list);
}
return ret;
}
}5.3、按之字形顺序打印二叉树
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
>输入 >{8,6,10,5,7,9,11} >返回值 >[[8],[10,6],[5,7,9,11]]
public class T59 {
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(pRoot);
boolean reverse = false;
while (! queue.isEmpty()) {
ArrayList<Integer> list = new ArrayList<>();
int cnt = queue.size();
while (cnt-- > 0) {
TreeNode node = queue.poll();
if (node == null) continue;
list.add(node.val);
queue.add(node.left);
queue.add(node.right);
}
if (reverse) Collections.reverse(list);
reverse = !reverse;
if (list.size() != 0) ret.add(list);
}
return ret;
}5.4 二叉树的右视图
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
>输入: [1,2,3,null,5,null,4] >输出: [1, 3, 4] >解释: 1 <--- / \ >2 3 <--- \ \ 5 4 <---
层序遍历，只保留最后一个结点的值
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if (root == null) return ret;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
TreeNode t = queue.poll();
if (t.left != null) queue.add(t.left);
if (t.right != null) queue.add(t.right);
if (size == 0) ret.add(t.val);
}
}
return ret;
}
}5.5 二叉树的左视图
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if (root == null) return ret;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()){
int size = queue.size();
int tmp = size - 1;
while (size-- > 0){
TreeNode t = queue.poll();
if(t.left != null) queue.add(t.left);
if(t.right != null) queue.add(t.right);
if(tmp == size) ret.add(t.val);
}
}
return ret;
}
}6、二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜素树）
>输入 >[4,8,6,12,16,14,10] >返回值 >true
public class T23 {
public boolean VerifySquenceOfBST(int [] sequence) {
if (sequence == null || sequence.length == 0) return false;
return isBST(sequence, 0, sequence.length - 1);
}
private boolean isBST(int[] sequence, int first, int last) {
if (last - first <= 1) {
return true;
}
int rootVal = sequence[last];
int cutIndex = first;
while (cutIndex < last && sequence[curIndex] <= rootVal) { // 二叉搜索树特征
cutIndex++;
}
for (int i = cutIndedx; i < last; i++) {
if (sequence[i] < rootVal) return false;
}
return isBST(sequence, first, cutIndex - 1) && isBST(sequence, cutIndex, last - 1);
}
}7、二叉树中和为某一值的路径
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
>给定如下二叉树，以及目标和 target = 22， 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 >返回: >[ [5,4,11,2], [5,8,4,5] >]
public class T24 {
private ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
backtracking(root, target, new ArrayList<>());
return ret;
}
private void backtracking(TreeNode node, int target, ArrayList<Integer> path) {
if (node == null)
return;
path.add(node.val);
target -= node.val;
if (target == 0 && node.left == null && node.right == null) {
ret.add(new ArrayList<>(path));
} else {
backtracking(node.left, target, path);
backtracking(node.right, target, path);
}
path.remove(path.size() - 1);
}
}8、二叉搜索树的第k个结点
给定一棵二叉搜索树，请找出其中第k大的节点。
>输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 >输出: 4>输入: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 >输出: 4
class Solution {
private int ans = 0, count = 0;
public int kthLargest(TreeNode root, int k) {
// clarification: root == null? k <= 1?
helper(root, k);
return ans;
}
private void helper(TreeNode root, int k) {
if (root.right != null) helper(root.right, k);
if (++count == k) {
ans = root.val;
return;
}
if (root.left != null) helper(root.left, k);
}
}9.1、二叉树的深度
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
>输入 >{1,2,3,4,5,#,6,#,#,7} >返回值 >4
public class T38 {
public int TreeDepth(TreeNode root) {
// 递归取左和右的最大高度 + 1
return root == null ? 0 : 1 + Math.max(TreeDepth(root.left), TreeDepth(root.right));
}
}
// 迭代 bfs
class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
// 树不需要标记哦
queue.add(root);
int depth = 1;
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
TreeNode node = queue.poll();
if (node.left == null && node.right == null)
return depth;
if (node.left != null)
queue.add(node.left);
if (node.right != null)
queue.add(node.right);
}
depth++;
}
return depth;
}
}9.2 二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
>给定二叉树 1 / \ 2 3 / \ 4 5 >返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
class Solution {
// 定义最大高度
private int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
// 递归
Depth(root);
return max;
}
private int Depth(TreeNode root) {
// 递归结束条件
if (root == null) return 0;
// 递归左的高度
int l = Depth(root.left);
// 递归右的高度
int r = Depth(root.right);
// 每次保持最大高度
max = Math.max(max, l + r);
// 返回左和右的最大高度加1
return Math.max(l, r) + 1;
}
}10、平衡二叉树
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
>给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 >返回 true 。>给定二叉树 [1,2,2,3,3,null,null,4,4] 1 / \ 2 2 / \ 3 3 / \ 4 4 >返回 false 。
// 定义一个平衡标记，默认平衡
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);
// 绝对值是否大于1
if (Math.abs(left - right) > 1)
isBalanced = false;
// 返回左和右的最大高度加1
return 1 + Math.max(left, right);
}11.1 非递归前序
给你二叉树的根节点
root，返回它节点值的 前序 遍历。>输入：root = [1,null,2,3] >输出：[1,2,3]>输入：root = [] >输出：[]>输入：root = [1,2] >输出：[1,2]>输入：root = [1,null,2] >输出：[1,2]
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
// 用栈的思想
Stack<TreeNode> stack = new Stack<>();
// 我们知道，前序：根左右
// 添加根
stack.push(root);
while (!stack.isEmpty()) {
// 弹根
TreeNode node = stack.pop();
// 判断是否为空
if (node == null) continue;
// 不为空，加val加入列表
ret.add(node.val);
// 先添加右，后左，这样下次就能先弹左
stack.push(node.right);
stack.push(node.left);
}
return ret;
}11.2 后序
给定一个二叉树，返回它的 后序 遍历。
>输入: [1,null,2,3] 1 \ 2 / 3 >输出: [3,2,1]
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
// 还是栈思想，后序：左右根，倒过来：根右左：那么就是根前序的差不多
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node == null) continue;
ret.add(node.val);
// 这里先添加左，保证弹出的是右
stack.push(node.left);
stack.push(node.right);
}
// 翻转就是后序
Collections.reverse(ret);
return ret;
}11.3 中序
给定一个二叉树的根节点
root，返回它的 中序 遍历。>输入：root = [1,null,2,3] >输出：[1,3,2]>输入：root = [] >输出：[]>输入：root = [1,2] >输出：[2,1]>输入：root = [1,null,2] >输出：[1,2]
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if (root == null) return ret;
// 还是栈：中序：左根右
Stack<TreeNode> stack = new Stack<>();
// 虚拟结点
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
// 一直左
stack.push(cur);
cur = cur.left;
}
// 保证弹出的左
TreeNode node = stack.pop();
ret.add(node.val);
// 开始移动到右
cur = node.right;
}
return ret;
}12 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
>输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 >输出：3 >解释：节点 5 和节点 1 的最近公共祖先是节点 3 。>输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 >输出：5 >解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。>输入：root = [1,2], p = 1, q = 2 >输出：1
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null)
return root;
// 如果根等于p或者q，直接返回根
if (root == p || root == q)
return root;
// 递归左和pq比
TreeNode left = lowestCommonAncestor(root.left, p, q);
// 递归右和pq比
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 同时不为空，则为根
if (left != null && right != null)
return root;
// 左不空，则左
else if (left != null)
return left;
// 右不空，则右
else if (right != null)
return right;
return null;
}
}13. 合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
>输入: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 >输出: >合并后的树: 3 / \ 4 5 / \ \ 5 4 7
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null)
return null;
if (t1 == null)
return t2;
if (t2 == null)
return t1;
TreeNode root = new TreeNode(t1.val + t2.val);
root.left = mergeTrees(t1.left, t2.left);
root.right = mergeTrees(t1.right, t2.right);
return root;
}
}
public TreeNode mergeTrees2(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null)
return null;
if (t1 == null)
return t2;
if (t2 == null)
return t1;
// 先合并根节点
t1.val += t2.val;
// 再递归合并左右子树
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
}
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(t1);
queue.offer(t2);
while(!queue.isEmpty()){
TreeNode node1 = queue.poll();
TreeNode node2 = queue.poll();
//合并两个值
node1.val += node2.val;
//左子树都不为空
if(node1.left != null && node2.left!=null){
queue.offer(node1.left);
queue.offer(node2.left);
}
if(node1.left == null)
node1.left = node2.left;
//右子树都不为空
if(node1.right != null && node2.right != null){
queue.offer(node1.right);
queue.offer(node2.right);
}
if(node1.right == null)
node1.right = node2.right;
}
return t1;
}
}14. 不同的二叉搜索树
给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
>输入: 3 >输出: 5 >解释: >给定 n = 3, 一共有 5 种不同结构的二叉搜索树: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
动态规划
假设n个节点存在二叉排序树的个数是G(n)，令f(i)为以i为根的二叉搜索树的个数
即有:G(n) = f(1) + f(2) + f(3) + f(4) + … + f(n)
n为根节点，当i为根节点时，其左子树节点个数为[1,2,3,…,i-1]，右子树节点个数为[i+1,i+2,…n]，所以当i为根节点时，其左子树节点个数为i-1个，右子树节点为n-i，即f(i) = G(i-1)*G(n-i),
上面两式可得:G(n) = G(0)G(n-1)+G(1)(n-2)+…+G(n-1)*G(0)
class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <=n; i++){
for (int j = 1; j <= i; j++){
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
}222. 完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
>输入：root = [1,2,3,4,5,6] >输出：6>输入：root = [] >输出：0
class Solution {
public int countNodes(TreeNode root) {
return root == null ? 0 : 1 + countNodes(root.left) + countNodes(root.right);
}
}98. 验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。>输入: 2 / \ 1 3 >输出: true>输入: 5 / \ 1 4 / \ 3 6 >输出: false >解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ，但是其右子节点值为 4 。
class Solution {
public boolean isValidBST(TreeNode root) {
return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean validate(TreeNode node, long min, long max) {
if (node == null)
return true;
if (node.val <= min || node.val >= max)
return false;
return validate(node.left, min, node.val) && validate(node.right, node.val, max);
}
}257. 二叉树的所有路径
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
>输入: 1 / \ >2 3 \ 5 >输出: ["1->2->5", "1->3"] >解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
class Solution {
private List<String> res = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
dfs(root, new StringBuilder());
System.out.println(res.toString());
return res;
}
public void dfs(TreeNode node, StringBuilder path) {
if (node == null)
return;
path.append(node.val);
if (node.left == null && node.right == null) {
res.add(path.toString());
return;
} else {
dfs(node.left, new StringBuilder(path).append("->"));
dfs(node.right, new StringBuilder(path).append("->"));
}
// path.deleteCharAt(path.length() - 1);
}
}124. 二叉树中的最大路径和
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
>输入：root = [1,2,3] >输出：6 >解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6>输入：root = [-10,9,20,null,null,15,7] >输出：42 >解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
class Solution {
int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
help(root);
return max;
}
int help(TreeNode root) {
if (root == null)
return 0;
int left = help(root.left);
int right = help(root.right);
max = Math.max(max, left + right + root.val);
int res = root.val + Math.max(left, right);
return res > 0 ? res : 0;
}
}814. 二叉树剪枝
给定二叉树根结点 root ，此外树的每个结点的值要么是 0，要么是 1。
返回移除了所有不包含 1 的子树的原二叉树。
( 节点 X 的子树为 X 本身，以及所有 X 的后代。)
>输入: [1,null,0,0,1] >输出: [1,null,0,null,1]>输入: [1,0,1,0,0,0,1] >输出: [1,null,1,null,1]>输入: [1,1,0,1,1,0,1,0] >输出: [1,1,0,1,1,null,1]
class Solution {
public TreeNode pruneTree(TreeNode root) {
if (root == null)
return null;
root.left = pruneTree(root.left);
root.right = pruneTree(root.right);
if (root.left == null && root.right == null && root.val == 0)
return null;
return root;
}
}1026. 节点与其祖先之间的最大差值
给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。
（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）
>输入：root = [8,3,10,1,6,null,14,null,null,4,7,13] >输出：7 >解释： >我们有大量的节点与其祖先的差值，其中一些如下： >|8 - 3| = 5 >|3 - 7| = 4 >|8 - 1| = 7 >|10 - 13| = 3 >在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。>输入：root = [1,null,2,null,0,3] >输出：3
class Solution {
public int maxAncestorDiff(TreeNode root) {
int left = dfs(root.left, root.val, root.val);
int right = dfs(root.right, root.val, root.val);
return Math.max(left, right);
}
public int dfs(TreeNode root, int max, int min) {
if (root == null)
return 0;
max = Math.max(root.val, max);
min = Math.min(root.val, min);
if (root.left == null && root.right == null)
return max - min;
int left = dfs(root.left, max, min);
int right = dfs(root.right, max, min);
return Math.max(left, right);
}
}本博客所有文章除特别声明外，大部分为学习心得，欢迎与博主联系讨论