牛客小题练手 | 二叉树（一）

专栏： 小题练手

 🌈刷题，面试，求职，快来牛客网一起成为offer收割机！

点击注册收割offerhttps://link.csdn.net/?target=https%3A%2F%2Fwww.nowcoder.com%2Flink%2Fpc_csdncpt_whispar_c

一、 剑指offer 55 ----二叉树的深度

难度： 简单

输入一棵二叉树，求该树的深度。

从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度，根节点的深度视为 1 。进阶：空间复杂度 O(1) ，时间复杂度 O(n）

假如输入的用例为{1,2,3,4,5,#,6,#,#,7}，那么如下图 :

点击下方链接跳转做题 🔻 JZ 55 二叉树的深度http://q8t.cn/Vdcip

step 1：对于每个节点，若是不为空才能累计一次深度，若是为空，返回深度为0.

 step 2：递归分别计算左子树与右子树的深度。

 step3：当前深度为两个子树深度较大值.

选择左右子树中深度较大者值 + 1即为二叉树的深度

public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root == null){
            return  0;
        }
        int leftLen = TreeDepth(root.left);
        int rightLen = TreeDepth(root.right);
        return leftLen > rightLen ? leftLen+1:rightLen +1;
    }
}

二、 剑指offer 15 ---- 相同的二叉树

难度：简单

给定两个根结点分别为 root1和 root2二叉树，请判断这两棵树是否完全相同。

数据范围:−10^4 ≤ Node.val ≤ 10^4    ， 两棵树上的节点数目都在范围 [0, 100] 内

  两个树在结构上相同，并且节点具有相同的值，故认为它们是相同的。

点击下方链接跳转做题 🔻

NC315 相同的二叉树http://q8t.cn/rJpfk

1.  一颗树为空，一颗不为空，返回false

2.  如果两颗都为空，则返回true

3.  如果val值不相同，则两棵树不相同

4 . 左右子树都相同,则两棵树相同

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root1 TreeNode类 
     * @param root2 TreeNode类 
     * @return bool布尔型
     */
    public boolean isSameTree (TreeNode root1, TreeNode root2) {
        // write code here
        if(root1 == null&&root2 != null || root1 != null&&root2 == null){
            return false;
        }
        if(root1 == null && root2 == null){
            return true;
        }
        if(root1.val != root2.val){
            return false;
        }
        return isSameTree(root1.left,root2.left)&&isSameTree(root1.right,root2.right);
    }
    }

三 、二叉树的中序遍历

难度：简单

给定一个二叉树的根节点root，返回它的中序遍历结果。 

数据范围：树上节点数满足 0 ≤n≤1000，树上每个节点的值满足 -1000 ≤n≤1000，进阶：空间复杂度 O(n)，时间复杂度 O(n)

点击下方链接跳转做题 🔻
NC161 二叉树的中序遍历http://q8t.cn/NAXD7

• step 1：准备数组用来记录遍历到的节点值
• step 2：从根节点开始进入递归，遇到空节点就返回，否则优先进入左子树进行递归访问。
• step 3：左子树访问完毕再回到根节点访问。
• step 4：最后进入根节点的右子树进行递归
• 准备一个和list大小一致的数组储存，并返回数组

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
     public void inOrder(List<Integer> list,TreeNode root){
         if(root == null){
             return ;
         }
         inOrder(list,root.left);
         list.add(root.val);
         inOrder(list,root.right);
     }
    public int[] inorderTraversal (TreeNode root) {
        // write code here
        List<Integer> list = new ArrayList<>();
        inOrder(list,root);
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++)
            res[i] = list.get(i);
        return res;
    }
    
}

• 使用list直接储存时

  public List<Character> preOrder2(TreeNode root){
        List<Character> ret = new ArrayList<>();
        if(root == null){
            return ret;
        }
        List<Character> leftTree = preOrder2(root.left);
        ret.addAll(leftTree);
        ret.add(root.val);
        List<Character> rightTree  = preOrder2(root.right);
        ret.addAll(rightTree);
        return ret;
    }