代码编织梦想

总结先放在前面:

本篇中练习了如下题目:
判断二叉树是否对称——NO.101. 对称二叉树
判断二叉树的子树——NO.100. 相同的树,NO.572. 另一棵树的子树
计算二叉树的深度和高度——NO.104. 二叉树的最大深度,NO.111.二叉树的最小深度
判断二叉树是否平衡——NO.110. 平衡二叉树
寻找二叉树的所有路径——NO.257. 二叉树的所有路径

解答二叉树时的一些小技巧与注意点:

感受递归的三部曲:
1.确定递归函数的参数和返回值
2.确定终止条件
3.确定单层递归的逻辑

题目实战

1.NO.101. 对称二叉树

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public bool IsSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        return myIsSymmetric(root.left,root.right);
    }

    public bool myIsSymmetric(TreeNode left,TreeNode right){
        if(left==null&&right!=null){    //左空,右非空,返回false
            return false;
        }
        else if(left!=null&&right==null){//左非空,右空,返回false
            return false;
        }
        else if(left==null&&right==null){//左右均空返回true
            return true;
        }
        else if(left.val==right.val){   //左右均非空,比较值,如果相等再递归
            return myIsSymmetric(left.left,right.right)&&myIsSymmetric(left.right,right.left);
        }
        return false;
    }
}

在这里插入图片描述

2.NO.100. 相同的树

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public bool IsSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q!=null){
            return false;
        }
        else if(p!=null&&q==null){
            return false;
        }
        else if(p==null&&q==null){
            return true;
        }
        else if(p.val==q.val){
            return IsSameTree(p.left,q.left)&&IsSameTree(p.right,q.right);
        }
        return false;
    }
}

在这里插入图片描述

3.NO.572. 另一棵树的子树

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public bool IsSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null&&subRoot!=null){
            return false;
        }
        if(IsSameTree(root,subRoot)==true){
            return true;
        }
        return IsSubtree(root.left,subRoot)||IsSubtree(root.right,subRoot);
    }

    public bool IsSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q!=null){
            return false;
        }
        else if(p!=null&&q==null){
            return false;
        }
        else if(p==null&&q==null){
            return true;
        }
        else if(p.val==q.val){
            return IsSameTree(p.left,q.left)&&IsSameTree(p.right,q.right);
        }
        return false;
    }
}

在这里插入图片描述

4.NO.104. 二叉树的最大深度

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int MaxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        return Math.Max(MaxDepth(root.left)+1,MaxDepth(root.right)+1);
    }
}

在这里插入图片描述

5.NO.559. N 叉树的最大深度

在这里插入图片描述

/*
// Definition for a Node.
public class Node {
    public int val;
    public IList<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, IList<Node> _children) {
        val = _val;
        children = _children;
    }
}
*/

public class Solution {
    public int MaxDepth(Node root) {
        if(root==null){
            return 0;
        }
        int max = 0;
        foreach(Node child in root.children)
        {
            max=Math.Max(max, MaxDepth(child));
        }
        return max + 1;
    }
}

在这里插入图片描述

6.NO.111.二叉树的最小深度

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int MinDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        //不是叶子节点,继续
        else if(root.left==null&&root.right!=null){
            return MinDepth(root.right)+1;
        }

        else if(root.left!=null&&root.right==null){
            return MinDepth(root.left)+1;
        }

        return Math.Min(MinDepth(root.left)+1,MinDepth(root.right)+1);
    }
}

在这里插入图片描述

7.NO.222. 完全二叉树的节点个数

在这里插入图片描述
无脑层序遍历法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int CountNodes(TreeNode root) {
        Queue<TreeNode> que = new Queue<TreeNode>();
        int ans=0;
        if(root==null){
            return 0;
        }
        int count=0;
        que.Enqueue(root);
        while(que.Count!=0){
            count=que.Count;
            for(int i=0;i<count;i++){
                TreeNode tmpNode = que.Dequeue();
                ans++;
                if(tmpNode.left!=null){
                    que.Enqueue(tmpNode.left);
                }
                if(tmpNode.right!=null){
                    que.Enqueue(tmpNode.right);
                }
            }
        }
        return ans;
    }
}

在这里插入图片描述
递归法:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int CountNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        return 1+CountNodes(root.left)+CountNodes(root.right);
    }
}

在这里插入图片描述

8.NO.110. 平衡二叉树

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public bool IsBalanced(TreeNode root) {
        if(getDepth(root)==-1){
            return false;
        }
        return true;
    }

    public int getDepth(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftDepth=getDepth(root.left);
        int rightDepth=getDepth(root.right);
        //以-1来标记两边的长度相差超过1
        if(leftDepth==-1||rightDepth==-1||Math.Abs(rightDepth-leftDepth)>1){
            return -1;
        }
        return Math.Max(getDepth(root.left),getDepth(root.right))+1;
    }
}

在这里插入图片描述

9.NO.257. 二叉树的所有路径

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {

    public class myPath{
        public TreeNode cur;
        public string path;
        public myPath(TreeNode cur,string path){
            this.cur = cur;
            this.path = path;
        }
    }
    
    List<string> ans= new List<string>();
    public IList<string> BinaryTreePaths(TreeNode root) {
        if(root==null){
            return ans;
        }
        getPaths(new myPath(root,root.val.ToString()));
        return ans;
    }

    public void getPaths(myPath root){
        //如果左/右节点不为空,就将左/右节点加入,并且更新路径
        if(root.cur.left!=null){
            getPaths(new myPath(root.cur.left, root.path + "->" + root.cur.left.val.ToString()));
        }
        if(root.cur.right!=null){
            getPaths(new myPath(root.cur.right, root.path + "->" + root.cur.right.val.ToString()));
        }
        if(root.cur.left==null&&root.cur.right==null){
            ans.Add(root.path);
        }
    }
}

在这里插入图片描述

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45067603/article/details/119390324

二叉树的深度,平衡二叉树深度-爱代码爱编程

题目描述 输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。 算法: 1、如果树为空,则深度为0 2、如果树不是空,那么深度是左子树的深度+1或右

树的高度,深度,层数_爆发的~小宇宙的博客-爱代码爱编程

申明:本文高度,深度基数为1,但是在《数据结构与算法分析:java语言描述》这本书上,高度,深度的基数为0;两种记法都没有错,都可以用来描述树的性质,只需要标注(>0)或者(>=0)做一个区分和解释即可 节点n

计算二叉树高度的三种方法_hellodake的博客-爱代码爱编程_求二叉树的高度

  递归 public class 递归 { class TreeNode{ int val; TreeNode left; TreeNode right; public TreeNode(int value){ this.val=value; } } public int getHeight(TreeNode root

子树_真理的追求者的博客-爱代码爱编程

描述 控制台 245. 子树 有两个不同大小的二叉树: T1 有上百万的节点; T2 有好几百的节点。请设计一种算法,判定 T2 是否为 T1的子树。 样例 下面的例子中 T2 是 T1 的子树: 1 3 / \ / T1 = 2 3 T2 =

树的子树大小与深度_微风袭来的博客-爱代码爱编程_子树的深度

2281 树的Size之和 51nod 2281 这题用的是并查集的思想,由于给定了父子关系,所以很容易知道建立并查集,最后find每个数,并且find函数找到一次某个节点,就给这个节点计数一次,代表这个节点有这个子节点

树的理解(一):树的高度-爱代码爱编程

树的高度 树的高度的递归思想: 根据树的高度的定义,对于任意一个节点来说,树的高度都等于左子树和右子树中比较大的那个 + 该节点高度1之和。 如果节点为空节点,那么高度就为0,因此,树的高度可以利用递归思想求出: public int maxDepth(TreeNode root) { if(root == null) return 0

小算法:求一棵二叉树的高度以及求一个节点的左右子树的高度-爱代码爱编程

求一棵二叉树的高度以及求一个节点的左右子树的高度 前言: 最近在学习平衡二叉排序树时,在计算二树的高度时笔者学到了一种相当精妙的算法,在此分享一下。 问题: 根据如上图构建一棵二叉树,并求出它的高度。以及写两个方法,传一个节点,可以分别求出它左右子树的高度。 求树的高度 我们只需在树的节点类中写如下方法: 返回的是以当前节点为根节点的树的高度 pu

力扣【104】二叉树的最大深度-爱代码爱编程

题目: 给定一个二叉树,找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,null,null,15,7],     3    / \   9  20     /  \    15   7 返回它的最大深度 3 。 题解: /** * Def

二叉树的高度_算法题(二叉树):平衡二叉树-爱代码爱编程

题目描述         输入一棵二叉树,判断该二叉树是否是平衡二叉树。         在这里,我们只需要考虑其平衡性,不需要考虑其是不是排序二叉树 解答         平衡二叉树定义(AVL):它或者是一颗空树,或者具有以下性质的二叉排序树:它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1,且它的左子树和右

求二叉树左右子树高度差_算法篇:树之树的高度-爱代码爱编程

算法: 这一类题目很简单,不过却是树的最基本操作之一,引申为判断树是不是平衡二叉树。 一般做法是,计算二叉树的左右子树的高度+1,然后取它们的最大值或者最小值。 题目1: https://leetcode-cn.com/problems/balanced-binary-tree/ 代码实现: /** * Defi