菜单

LeetCode 笔记— 二叉树

duckflew
发布于 2021-03-21 / 278 阅读
0
0

LeetCode 笔记— 二叉树

LeetCode 笔记--- 二叉树

501.求BST的众数

这个题不需要另外定义一个map 会造成空间的浪费 因为根据BST的特性 中序遍历 相同的元素都是排在一起的 所以只需要维护一个maxNum curNum cur
遍历到不同的元素 就刷新cur curnum复位为1 并且和Maxnum比较 如果相同 就加入到结果数组 如果不相同 就把结果数组清空 再加入

 private int cur;
    private int curNum;
    private int maxNum=-1;
    private List<Integer>res;
    public int[] findMode(TreeNode root) {
        res=new ArrayList<>();
        dfs(root);
        int []ans=new int[res.size()];
        if (res.size()>0)
        for (int i = 0; i < ans.length; i++)
        {
            ans[i]=res.get(i);
        }
        return ans;
    }
    public void dfs(TreeNode root)
    {
        if (root==null)return ;
        dfs(root.left);
        update(root.val);
        dfs(root.right);

    }
    public void update(int val)
    {
        if (val!=cur)
        {
            cur=val;
            curNum=1;
        }
        else
        {
            curNum++;
        }
        if (curNum>maxNum)
        {
            res.clear();
            res.add(cur);
            maxNum=curNum;
        }
        else if (curNum<maxNum)
        {

        }
        else
        {
            res.add(cur);
        }
    }

109.有序链表转化为BST

给定的有序链表: [-10, -3, 0, 5, 9],
一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树:

      0
     / \
   -3   9
   /   /
 -10  5

快慢指针加分治法
首先求出链表的中间节点作为树的根节点 然后以Mid节点为界 对左右两个链表采取同样的方法

 public   TreeNode sortedListToBST(ListNode head) {
        return buildTree(head,null);
    }
    public  TreeNode buildTree(ListNode left,ListNode right)
    {
        if (left==right)return null;
        ListNode mid = findMidListNode(left, right);
        TreeNode newNode = new TreeNode(mid.val);
        newNode.left=buildTree(left,mid);
        newNode.right=buildTree(mid.next,right);
        return newNode;
    }
    public  ListNode findMidListNode(ListNode left,ListNode right)
    {
        if (left==right)return null;
        ListNode slow=left;
        ListNode fast=left;
        while (fast!=right&&fast.next!=right)
        {
            slow=slow.next;
            fast=fast.next;
            fast=fast.next;
        }
        return slow;
    }

538.把二叉搜索树转化为累加树

要把一个BST转化为每个节点值变成大于等于原节点元素的树 只需要倒序遍历 维护一个sum变量 到哪个点了就root.val=root.val+sum
tips 这里的倒序不是说的后序遍历 而是说 逆中序遍历 即为先遍历right子树

230.求二叉搜索树的第K个最小的元素

这个题就是中序遍历 然后用一个hasReadNum作为标志表示当前你已经遍历到第几个元素了 如果是第k个 返回就是了 如果大于 直接返回 相当于剪枝

 private int hasReadNum;
    int res;
    public int kthSmallest(TreeNode root, int k) {
         res=0;
        hasReadNum=0;
        dfs(root,k);
        return res;
    }
    public void dfs(TreeNode root,int k)
    {
        if (root==null)return ;
        dfs(root.left,k);
        hasReadNum++;
        if (hasReadNum==k)
        {
            res=root.val;
            return ;
        }
        else if (hasReadNum>k)
        {
            return;
        }
        dfs(root.right,k);
    }

669.修剪二叉搜索树

给你二叉搜索树的根节点 root ,同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树,使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构(即,如果没有被移除,原有的父代子代关系都应当保留)。 可以证明,存在唯一的答案。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意,根节点可能会根据给定的边界发生改变。

思路: 假设trimBST的结果是理想的 判断一下我当前节点 的值 如果root.val<l说明只需要考虑右子树 左子树已经不符合了 这是搜索树的性质 同理 如果root.val>R 那只需要判断左子树

 public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root==null)return null;
        if (root.val>high)return trimBST(root.left,low,high);
        if (root.val<low)return trimBST(root.right,low,high);
        root.left=trimBST(root.left,low,high);
        root.right=trimBST(root.right,low,high);
        return root;
    }

637.二叉树的层平均值

BFS遍历每一层 需要注意的是 每一次Poll元素之前先记录一下此时的queue有多少个元素 这个个数就是本层有多少个元素 sum就+ 这么多次 然后sum/num 就是本层平均值了 在循环内部其实还是正常的BFS该添加元素就元素 因为队列的特性是可以记录的每一层的 513题的找最后一层最左边的元素也是这个方法 判断i==0 也就是每一层的第一个元素的时候 就更新一次答案就行了

 public  List<Double> averageOfLevels(TreeNode root) {
        if (root==null)return null;
        List<Double>averages=new ArrayList<>();
        Queue<TreeNode>queue=new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty())
        {
            long levelSum=0;
            int levelNum=queue.size();
            for (int i = 0; i < levelNum; i++)
            {
                TreeNode top = queue.poll();
                levelSum+=top.val;
                if (top.left!=null)queue.add(top.left);
                if (top.right!=null)queue.add(top.right);
            }
            averages.add(levelSum/(levelNum*1.0));
        }
        return averages;
    }

687.最长同值路径

给定一个二叉树,找到最长的路径,这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意:两个节点之间的路径长度由它们之间的边数表示

也是找2个节点之间的一条路径 这条路径上的所有的节点的值都是相同的

private int max=Integer.MIN_VALUE;
    public int longestUnivaluePath(TreeNode root) {
       if (root==null)return 0;
       postOrder(root);
       return max;
    }
    public int postOrder(TreeNode root)
    {
        if (root==null)
        {
            return 0;
        }
        int leftArrow=0;
        int rightArrow=0;
        int leftValue=postOrder(root.left);
        int rightValue=postOrder(root.right);
        if (root.left!=null&&root.left.val==root.val)
        {
            leftArrow=(leftValue+1);
        }
        if (root.right!=null&&root.right.val==root.val)
        {
            rightArrow=(rightValue+1);
        }
        max=Math.max(max,leftArrow+rightArrow);
        return Math.max(leftArrow,rightArrow);
    }

这个题和以前的求最长的路径有点像
递归回溯每个节点 返回的都是这个节点上 左右单支能够取到的最长路径的长度
如果我本节点的值和我的左子树的最长同值路径相等 那就让leftArrow=leftValue+1 也就是得到了现在的左边的最长的同值路径 同理可以得到最长的右边的同值路径 leftArrow 把这俩加起来 同max做比较 更新max的值 最后对于这个节点 返回的还是leftarrow 和rightarrow中较大的那个 因为只能取单边路径

404.左叶子之和

private int sum;
    public int sumOfLeftLeaves(TreeNode root) {
        sum=0;
        fun(root,false);
        return sum;
    }
    public void fun(TreeNode root,boolean isLeft)
    {
        if (root==null)return ;
        if (isLeft&&root.left==null&&root.right==null)
        {
            sum+=root.val;
            return ;
        }
        fun(root.left,true);
        fun(root.right,false);
    }

101.对称二叉树

给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

一棵树满足镜像对称 就是说他的两个子树需要镜像对称
两颗树需要镜像对称 条件有三个

  • 根节点的值相等
  • a树的左子树与b树的右子树镜像对称
  • a树的右子树与b树的左子树镜像对称

如此一来就可以写成递归的形式了

 public boolean isSymmetric(TreeNode root) {
        if (root==null)return true;
        return twoTreeIsMirroring(root.left,root.right);
    }
    public boolean twoTreeIsMirroring(TreeNode t1,TreeNode t2)
    {
        if (t1==null&&t2==null)return true;
        if (t1==null||t2==null)return false;
        return t1.val==t2.val&&twoTreeIsMirroring(t1.left, t2.right)&&twoTreeIsMirroring(t1.right,t2.left);
    }

572.另一个树的子树

暴力解法写了 还没写更好的算法测试
暴力法如下
遍历第一棵树的每个节点依次判断这个节点为root的子树是否与另外一颗树相等
treeEquals就是判断相等的方法

public boolean isSubtree(TreeNode s, TreeNode t) {
        if (t==null)return true;
        /**
         * 如果t等于null 那么t就是任何树的子树  因为 任何一棵树都有null节点
         */
        if (s==null)return false;
        /**
         * 如果s==null 那么s不可能有子树 除非t也等于null 但是这种情况在前面已经是判断了的
         */
        return treeEquals(s, t)||isSubtree(s.left,t)||isSubtree(s.right,t);
    }

    /**
     * 判断树是否相等的递归函数
     * @param t1
     * @param t2
     * @return
     */
    public boolean treeEquals(TreeNode t1,TreeNode t2)
    {
        if (t1==null)return t2==null;  //同时为null 相等
        if (t2==null)return false;  //后面的为Null  就不相等
        if (t1.val!=t2.val)return false;  //两个根节点的值不相等那就是两棵树不相等
        /**
         * 然后递归 左子树和柚子树  只有左右子树同时相等 树才能相等
         */
        return treeEquals(t1.left,t2.left)&&treeEquals(t1.right,t2.right);
        
    }

112.路径总和

给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树,以及目标和 sum = 22,

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \      \
    7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

这个题符合递归的思想 要找树的路径上的节点值之和是否等于某个值sum 换个角度来说 就是找 左右子树有的路径上的节点之和是否等于某个sum-root.val
递归终点就是 如果当前是叶子节点了 就判断当前的root.val是否等于sum

public boolean hasPathSum(TreeNode root, int sum) {
        if (root==null)return false;
        if (root.left==null&&root.right==null)return sum==root.val;
        return (hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val));
    }

非递归写法 利用广度优先遍历 把每个节点到root节点的节点值之和存起来 两个队列里面11对应 遍历到叶子节点就判断一下 如果满足条件就返回
如果遍历完了都没返回 说明不存在 就返回 false

public boolean hasPathSum(TreeNode root, int sum) {
        if (root==null)return false;
        Queue<TreeNode> nodeQueue=new ArrayDeque<>();
        Queue<Integer>pathQueue=new ArrayDeque<>();
        nodeQueue.add(root);
        pathQueue.add(root.val);
        while (!nodeQueue.isEmpty())
        {
            TreeNode cur=nodeQueue.poll();
            int curSum=pathQueue.poll();
            if (cur.left==null&&cur.right==null&&curSum==sum)
                return true;
            if  (cur.left!=null)
            {
                nodeQueue.add(cur.left);
                pathQueue.add(curSum+cur.left.val);
            }
             if  (cur.right!=null)
            {
                nodeQueue.add(cur.right);
                pathQueue.add(curSum+cur.right.val);
            }
        }
        return false;
    }

617.合并二叉树

给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:
输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/
4 5
/ \ \
5 4 7

public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1==null&&t2==null)return null;
        else if (t1==null)return t2;
        else if (t2==null)return t1;
        else 
        {
            TreeNode newNode = new TreeNode(t1.val + t2.val);
            newNode.left=mergeTrees(t1.left,t2.left);
            newNode.right=mergeTrees(t1.right,t2.right);
            return newNode;
        }
    }

226.翻转二叉树

public TreeNode invertTree(TreeNode root) {
        invertTreeNode(root);
        return root;
    }
    public void invertTreeNode(TreeNode root)
    {
        if (root==null)return ;
        invertTree(root.left);
        invertTree(root.right);
        TreeNode temp=root.left;
        root.left=root.right;
        root.right=temp;
    }

谷歌:我们90%的工程师使用您编写的软件(Homebrew),但是您却无法在面试时在白板上写出翻转二叉树这道题,这太糟糕了。

刷完这个题说明我已经超越了世界级大牛了

543.二叉树的直径

二叉树的直径定义为任意两个节点之间的距离的最大值
做法就是递归二叉树 返回左右子树种 单支的长度的较大值+1 就是本节点开始的单支的长度 然后维护一个max值 每次遍历到节点就更新一次max的值 max与left单支的长度+right单支的长度+1 比较 取较大值 其实这个题可以看成是 找所有的节点中左右字数高度和最长的那个节点
代码如下

int max;
    public int diameterOfBinaryTree(TreeNode root)
    {
        if (root==null)return 0;
        maxDanZhi(root);
        return max-1;
    }
    public int maxDanZhi(TreeNode root)
    {
        if (root==null)return 0;
        int left=maxDanZhi(root.left);
        int right=maxDanZhi(root.right);
        max=Math.max(max,left+right+1);
        return Math.max(left,right)+1;
    }

110.判断一棵二叉树是否是平衡二叉树

最优的方法是采用后序遍历 统计左右子树的深度 如果左右子树的深度有一个是-1 说明在子树里面有已经有节点不满足平衡二叉树的定义了 那这棵树也返回-1就可以了 如果 两个深度都不是-1 那就判断他们的差是不是0或者1,如果不是 又不满足 还是返回-1 满足的话 则求出本树的深度 即为max(左子树的深度,右子树的深度)+1;

public int postOrder(TreeNode root)
{
    if (root==null)return 0;
    int leftDepth=postOrder(root.left);
    if (leftDepth==-1)return -1;
    int rightDepth=postOrder(root.right);
    if (rightDepth==-1)return -1;
    return Math.abs(leftDepth-rightDepth)<2?Math.max(leftDepth,rightDepth)+1:-1;
}
public boolean isBalanced(TreeNode root)
{
    return postOrder(root)!=-1;
}

104.二叉树的最大深度

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

二叉树的深度=max(左子树的深度右子树的深度)+1

public int maxDepth(TreeNode root) {
      if (root==null)return 0;
      return Integer.max(maxDepth(root.left),maxDepth(root.right))+1;
}


评论