最小子树——lintcode596

最小子树

题目:最小子树

给一棵二叉树, 找到和为最小的子树, 返回其根节点。

示例:

输入: {1,-5,2,1,2,-4,-5} 输出:1 说明 这棵树如下所示:      1    /     -5     2  /    /   1   2 -4  -5  整颗树的和是最小的,所以返回根节点1.

题解:分治法

public class Solution {     private TreeNode minRoot;     private int minSum;      public int dfs(TreeNode root) {         if (root == null) return 0;         int sum = dfs(root.left)+ dfs(root.right) + root.val;         if (sum < minSum) {             minSum = sum;             minRoot = root;         }         return sum;     }      public TreeNode findSubtree(TreeNode root) {         minRoot = root;         minSum=Integer.MIN_VALUE;         dfs(root);         return minRoot;     } }

推荐这些文章:

450. 删除二叉搜索树中的节点

递归
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {

if (root == null){
return root;
}

/**
* 如果大于当前节点,就在左子树寻找;小于则在右子树寻找
* 相等则分三种情况:如果有一个孩子为空,则让另一个孩子作为新的根节点;否则,让左子树的最小节点成为新的根节点
*/
if (root.val > key){...

【每日一题】【树的dfs递归,返回多次,注意都遍历完后才最终返回】2022年1月6日-112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。
叶子节点 是指没有子节点的节点。
来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/path-sum著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

 

 
答案:

/**
* Definition for a binary tre...

面试经典题:二叉树最近公共祖先

二叉树的最近公共祖先
面试经典题:最近公共祖先,提供三种思路:1、模拟路径,2、dfs,3、dfs优化
class Solution {
public:
bool dfs(TreeNode* root, TreeNode* t, vector<TreeNode*>&path){
if(!root) return false;
if(root == t){
path.push_back(root);
return true;
}
if(dfs(ro...

腾讯五十题 No.42 二叉树的最近公共祖先

题目链接
注意p,q必然存在树内, 且所有节点的值唯一!!!
递归思想, 对以root为根的(子)树进行查找p和q, 如果root == null || p || q 直接返回root
表示对于当前树的查找已经完毕, 否则对左右子树进行查找, 根据左右子树的返回值判断:
1. 左右子树的返回值都不为null, 由于值唯一左右子树的返回值就是p和q, 此时root为LCA
2. 如果左右子树返回值只有一个不为null, 说明只有p和q存在与左或右子树中, 最先找到的那个节点为LCA
3. 左右子树返回值均为null, p和q均不在树中, 返回null
class Solution {
...

783. 二叉搜索树节点最小距离 二叉树中序遍历

给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。
https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
...

129. Sum Root to Leaf Numbers

My first solution:

class Solution {
private int sum =0;
public int sumNumbers(TreeNode root) {
preOrder(root, "");
return sum;
}

private void preOrder(TreeNode root, String numString){
if(root==null)
return;
if(root.left==null&&a...

BM29 二叉树中和为某一值的路径(一)

/*
* function TreeNode(x) {
* this.val = x;
* this.left = null;
* this.right = null;
* }
*/

/**
*
* @param root TreeNode类
* @param sum int整型
* @return bool布尔型
*/
function hasPathSum( root , sum ) {
// write code here
if(root === null){
return false
}
...

腾讯五十题 No.28 二叉树中的最大路径和

题目链接
class Solution {

private int res = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
getMax(root);
return res;
}

private int getMax(TreeNode root){
if(root == null) return 0;
int left = Math.max(0,getMax(root.left));//左递归
int r...

腾讯五十题No.40二叉树搜索中第k小的元素

题目链接
二叉树特点左子树小于根节点根节点小于右子树
class Solution {
public int kthSmallest(TreeNode root, int k) {
//左子树节点个数
int leftN = findChild(root.left);
//如果k等于左子树节点加一,则第k个数为根节点
if(leftN + 1 == k) return root.val;
//如果小于左子树节点个数,就递归左子树
else if(k <= leftN){
...

Leetcode235/236之树最近公共祖先以及递归中带TreeNode

树最近公共祖先以及递归中带TreeNode

但递归时返回TreeNode要想清楚最后一步返回到哪

Leetcode236-二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {...

文章标题:最小子树——lintcode596
文章链接:https://www.dianjilingqu.com/2043.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>