二叉树的“查”

前言：今天来重点讲一下二叉树的“查”，二叉树也是一种数据存储方式，类比于数组来说，最基本的“查”应该有以下几种：

1. 二叉树的大小即节点个数
2. 二叉树的最大深度和最小深度
3. 二叉树的最近公共祖先

方法论：

本文中主要用到了两种思维模式，如下：

1. 是否遍历一遍二叉树就可以得到结果，如果可以，只需要对二叉树的递归遍历方式或者迭代遍历方式便可以可到结果，这种思维模式称为遍历思维模式
2. 是否需要借助子树的返回值？如果需要可以定义一个递归函数求解(注重逻辑的自洽)，这种思维模式下：递归函数需要返回值，代码通常写在后序位置，这种思维模式称为分治思维模式。

无论那种思维模式，你都需要思考：

如果单独抽出一个节点，他需要做什么事情，需要在前序、中序、后序哪个位置做事情？不同位置的代码仅能接收到该代码之前的结果，前序位置的代码自然接收不到子树的消息，因为前序代码执行的时候，二叉树还没有开始遍历。

一、二叉树的节点个数

1. 普通二叉树的节点个数

1.1 遍历的思维模式

• 递归方式

class Solution {
    int count = 0;
    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        count(root);
        return count;
    }
    void count(TreeNode root) {
        if(root == null) return;
        count(root.left);
        count(root.right);
        count++;//count++的位置在前、中、后序都可以放置，本质就是数组中的循环体中的count++
    }
}

• 迭代方式
  迭代方式，深度迭代和广度迭代都可以，只需要将迭代代码中的result.add(curNode.val)改为count++即可，具体代码可参考我的上一篇文章二叉树遍历。

1.2 分治的思维模式

首先思考：如果你是一个树节点，你如何知道以你为父节点的二叉树节点个数？你的子树需要给你返回什么？
我的思考：二叉树的节点个数 = 父节点 + 左子树节点个数 + 右子树节点大小

class Solution {
    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

2. 完全二叉树的节点个数

说完普通二叉树的节点个数，其实完全二叉树、满二叉树的节点个数也可以求，但是没有利用完全二叉树和满二叉树的性质，去提高减少代码的时间复杂度和空间复杂度。
既然要利用完全二叉树的性质，那就需要知道他的性质是什么：

1. 完全二叉树的子树必定可以分解为多个满二叉树，这里的子树也可以是子树的子树，单个节点也可以是满二叉树。
2. 满二叉树的节点个数: 2^h-1，这里的h是层数。root节点为第一层。
   知道了以上的性质，我们就不需要遍历左右子树，只需要知道满二叉子树的高度即可。

class Solution {
    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        int hl = 1; int hr = 1;//考虑极端情况，root.left == null或者root.right == null;
        TreeNode left = root.left;
        TreeNode right = root.right;
        while(left != null) {
            left = left.left;
            hl++;
        }
        while(right != null) {
            right = right.right;
            hr++;
        }
        if(hl == hr) return (2<<(hl-1)) - 1;//如果是满二叉树，按照2^h-1计算，2<<1等于2^2;
        //如果不是满二叉树，按照普通二叉树计算
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

3. 满二叉树的节点个数

class Solution {
    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        int h = 0;//考虑极端情况，root.left == null&&root.right == null;
        while(root != null) {
            root = root.left;
            h++;
        }
        return (2<<(h-1)) - 1;
    }
}

关于完全二叉树和满二叉树求深度h的代码总结：
明确一下几点：
1、root节点是谁？是root还是root.left还是root.right，即你所求二叉树的root节点是谁？
2、二叉树的h从0还是从1开始，我觉得这里的h代表的是所求二叉树的父节点层数-1，为什么减去1，是因为紧接着下面h++，这也就意味着只要你的root != null，就会+1。

二、二叉树的最大深度和最小深度

1. 二叉树的最大深度

1.1 遍历的思维模式

• 递归方式

1. 一遍遍历是否可以得到结果？可以，可以维护一个全局变量用来记录深度。
2. 记录什么的深度？自然是每个叶子节点的深度，然后取深度的最大值就是二叉树的最大深度。
3. 站在一个树节点的角度，深度该如何计算？进入节点的时候深度加1，离开节点的时候深度减1。

class Solution {
    int depth = 0;//当前叶子结点深度
    int max = 0;//全局最大深度
    public int maxDepth(TreeNode root) {
        traverse(root);
        return max;
    }
    void traverse(TreeNode root) {//
        if(root == null) {
            max = Math.max(depth,max);
            return;
        }
        depth++;//进入节点，深度+1
        traverse(root.left);
        traverse(root.right);
        depth--;//离开节点，深度-1
    }
}

• 迭代方式
  采用层序迭代的方式用来计算二叉树的最大深度最方便，因为层序迭代代码的内部会维护当前队列的大小，以一层为一个循环，仅需要维护一个全局变量depth，每次循环后加1便可以计算出二叉树的最大深度。

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;//维护全局深度变量，初始为层数-1，即1-1=0;
        while(!queue.isEmpty()) {
            int n = queue.size();
            for(int i=0; i<n; i++) {
                TreeNode curNode = queue.poll();
                if(curNode.left != null) queue.offer(curNode.left);
                if(curNode.right != null) queue.offer(curNode.right);
            }
            depth++;
        }
        return depth;
    }
}

只要涉及到深度相关的问题，要着重考虑初始深度h的取值，考虑极端情况去对h取值。

1.2 分治的思维模式

首先思考：如果你是一个树节点，你如何知道以你为父节点的二叉树深度？你的子树需要给你返回什么？
我的思考：二叉树的最大深度 = 父节点深度 + 左右子树深度的最大值

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

2. 二叉树的最小深度[重点复习

原创文章，作者：506227337，如若转载，请注明出处：https://blog.ytso.com/245440.html