二叉树（牛客）

2023-05-06 | 阅读：次

二叉树（牛客）

题目来自牛客题目库算法篇面试必刷TOP101。

BM23 二叉树的前序遍历(简单)

题目

题目链接

给你二叉树的根节点 root ，返回它节点值的前序遍历。

数据范围：二叉树的节点数量满足1≤n≤100 ，二叉树节点的值满足1≤val≤100 ，树的各节点的值各不相同

示例 1：

输入：{1,#,2,3}
返回值：[1,2,3]

解法1 递归

前序遍历：根-左-右

递归解题三步骤：终止条件、返回值、本级任务。

终止条件：节点为空
返回值：空
本级任务：根-左-右

import java.util.*;

public class Solution {

    public void preorder(List<Integer> list, TreeNode root){
        // 空节点处理不要忘了
        if(root == null)
            return;
        // add()方法添加元素
        list.add(root.val);
        preorder(list, root.left);
        preorder(list, root.right);
    }
    
    public int[] preorderTraversal (TreeNode root) {
        // list<Integer>是可变长度的数组
        List<Integer> list = new ArrayList();
        preorder(list, root);
        // 可变数组的元素个数用list.size()方法
        int[] res = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            res[i] = list.get(i);
        }
        return res;
    }
}

解法2 栈

前序遍历：根-左-右，所以父节点出栈后，子节点入栈顺序是右-左。

import java.util.*;

public class Solution {

    public int[] preorderTraversal (TreeNode root) {
        List<Integer> list = new ArrayList();
        Stack<TreeNode> stk = new Stack<TreeNode>();
        if(root == null)
            // 返回空数组
            return new int[0];
        stk.push(root);
        // 判断栈是否为空的方法stk.isEmpty()
        while(!stk.isEmpty()){
            TreeNode node = stk.pop();
            list.add(node.val);
            if(node.right != null)
                stk.push(node.right);
            if(node.left != null)
                stk.push(node.left);
        }
        int[] res = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            res[i] = list.get(i);
        }
        return res;
    }
}

用栈解决二叉树的后序遍历和前序遍历思路一样，所以先写BM25后序遍历，再写BM24中序遍历。

BM25 二叉树的后序遍历(简单)

给定一个二叉树，返回他的后序遍历的序列。

后序遍历是值按照左节点->右节点->根节点的顺序的遍历。

数据范围：二叉树的节点数量满足1≤n≤100 ，二叉树节点的值满足1≤val≤100 ，树的各节点的值各不相同

样例图：

示例：

示例1：
输入：{1,#,2,3}
返回值：[3,2,1]
说明：如题面图 
示例2：
输入：{1}
返回值：[1]

解法1 递归

递归解题三步骤：终止条件、返回值、本级任务。

import java.util.*;

public class Solution {

    public void postorder(List list, TreeNode node) {
        // 空节点处理不要忘了
        if(node == null)
            return ;
        postorder(list, node.left);
        postorder(list, node.right);
        list.add(node.val);
    }

    public int[] postorderTraversal (TreeNode root) {
        List<Integer> list = new ArrayList();
        postorder(list, root);
        int[] res = new int[list.size()];
        for(int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

解法2 栈

前序遍历是根-左-右，先变成根-右-左，再反转为左-右-根，即后序遍历。

import java.util.*;

public class Solution {

    public int[] postorderTraversal (TreeNode root) {
        if(root == null)
            return new int[0];
        List<Integer> list = new ArrayList();
        Stack<TreeNode> stk = new Stack<TreeNode>();
        stk.push(root);
        while(!stk.isEmpty()){
            TreeNode node = stk.pop();
            list.add(node.val);
            if(node.left != null)
                stk.push(node.left);
            if(node.right != null)
                stk.push(node.right);
        }
        // 用下面的方式反转List
        Collections.reverse(list);
        int[] res = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            res[i] = list.get(i);
        }
        return res;
    }
}

BM24 二叉树的中序遍历(中等)

中等的原因是用栈迭代。

题目

题目链接

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

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

示例：

示例1：
输入：{1,2,#,#,3}
返回值：[2,3,1]
示例2：
输入：{1,2}
返回值：[2,1]
示例3：
输入：{}
返回值：[]
示例4：
输入：{1,#,2}
返回值：[1,2]

备注：
树中节点数目在范围[0, 100]内
树中的节点的值在[-100,100]以内

解法1 递归

递归解题三步骤：终止条件、返回值、本级任务。

import java.util.*;

public class Solution {

    public void inorder(List list, TreeNode node){
        if(node == null)
            return ;
        inorder(list, node.left);
        list.add(node.val);
        inorder(list, node.right);
    }
    public int[] inorderTraversal (TreeNode root) {
        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;
    }
}

解法2 栈

使用指针cur指向节点，用来访问节点。

import java.util.*;

public class Solution {

    public int[] inorderTraversal (TreeNode root) {
        if(root == null)
            return new int[0];
        List<Integer> list = new ArrayList();
        Stack<TreeNode> stk = new Stack<TreeNode>();
        TreeNode cur = root;
        // 当前指针指向的节点不为空，或栈不为空时
        while(cur != null || !stk.isEmpty()){
            // 处理左子树
            while(cur != null) {
                stk.push(cur);
                cur = cur.left;
            }
            // 处理父节点
            TreeNode node = stk.pop();
            list.add(node.val);
            // 处理右子树
            cur = node.right;
        }
        int[] res = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            res[i] = list.get(i);
        }
        return res;
    }
}

BM26 求二叉树的层序遍历(简单)

题目

题目链接

给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）例如：给定的二叉树是{3,9,20,#,#,15,7}, 该二叉树层序遍历的结果是 [ [3], [9,20], [15,7]

]

提示:

0 <= 二叉树的结点数 <= 1500

示例：

示例1：
输入：{1,2}
返回值：[[1],[2]]
示例2：
输入：{1,2,3,4,#,#,5}
返回值：[[1],[2,3],[4,5]]

解法1 队列

使用队列储存二叉树节点。记录二叉树每一层的节点数目。

import java.util.*;

public class Solution {

    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // 注意声明的语句
        ArrayList<ArrayList<Integer>> res = new ArrayList();
        if(root == null)
            return res;
        // 使用队列，注意声明的语句
        Queue<TreeNode> q = new ArrayDeque<TreeNode>();
        q.add(root);
        while(!q.isEmpty()){
            ArrayList<Integer> row = new ArrayList();
            // 层序遍历需要记录当前层的节点数目
            int n = q.size();
            for(int i = 0; i < n; i++){
                // 注意队列的操作poll()
                TreeNode cur = q.poll();
                row.add(cur.val);
                if(cur.left != null)
                    q.add(cur.left);
                if(cur.right != null)
                    q.add(cur.right);
            }
            // 注意给二维数组赋值的操作
            res.add(row);
        }
        return res;
    }
}

解法2 递归

递归解题三步骤：终止条件、返回值、本级任务。

终止条件：节点为空
返回值：空
本级任务：处理当前层

import java.util.*;

public class Solution {

    ArrayList<ArrayList<Integer>> res = new ArrayList();

    void traverse(TreeNode root, int depth) {
        if(root == null)
            return ;
        // 新的一层，加一层
        if(res.size() < depth){
            ArrayList<Integer> row = new ArrayList();
            res.add(row);
            row.add(root.val);
        }
        // 不是新的一层，先获取所在的层，再把节点值加到层末尾
        else {
            ArrayList<Integer> row = res.get(depth - 1);
            row.add(root.val);
        }
        // 遍历左右子树
        traverse(root.left, depth + 1);
        traverse(root.right, depth + 1);
    }

    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        if(root == null)
            return res;
        traverse(root, 1);
        return res;
    }
}

BM27 按之字形顺序打印二叉树(中等)

题目

题目链接

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

数据范围：0≤n≤1500,树上每个节点的val满足∣val∣<=1500 要求：空间复杂度: O(n)，时间复杂度：O(n)

例如：给定的二叉树是{1,2,3,#,#,4,5}

该二叉树之字形层序遍历的结果是

[

[1],

[3,2],

[4,5]

]

示例：

示例1：
输入：{1,2,3,#,#,4,5}
返回值：[[1],[3,2],[4,5]]
说明：如题面解释，第一层是根节点，从左到右打印结果，第二层从右到左，第三层从左到右。 
示例2：
输入：{8,6,10,5,7,9,11}
返回值：[[8],[10,6],[5,7,9,11]]
示例3：
输入：{1,2,3,4,5}
返回值：[[1],[3,2],[4,5]]

解法1 队列

和层序遍历一样，但隔一层反转一次。

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList();
        if (pRoot == null)
            return res;
        int num = 0;
        Queue<TreeNode> q = new ArrayDeque<TreeNode>();
        q.add(pRoot);
        while (!q.isEmpty()) {
            ArrayList<Integer> row = new ArrayList();
            num++;
            int n = q.size();
            for (int i = 0; i < n; i++) {
                TreeNode cur = q.poll();
                row.add(cur.val);
                if (cur.left != null)
                    q.add(cur.left);
                if (cur.right != null)
                    q.add(cur.right);
            }
            // 反转
            if (num % 2 == 0)
                Collections.reverse(row);
            res.add(row);
        }
        return res;
    }
}

解法2 栈

和层序遍历一样，但隔一层反转一次

import java.util.*;

public class Solution {
    ArrayList<ArrayList<Integer>> res = new ArrayList();

    void traverse(TreeNode root, int depth) {
        if (root == null)
            return ;
        if (res.size() < depth) {
            ArrayList<Integer> row = new ArrayList();
            res.add(row);
            row.add(root.val);
        } else {
            ArrayList<Integer> row = res.get(depth - 1);
            row.add(root.val);

        }
        traverse(root.left, depth + 1);
        traverse(root.right, depth + 1);
    }

    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        if (pRoot == null)
            return res;
        traverse(pRoot, 1);
        // 反转
        for (int i = 0; i < res.size(); i++) {
            if (i % 2 == 1) {
                Collections.reverse(res.get(i));
            }
        }
        return res;
    }
}

BM28 二叉树的最大深度(简单)

题目

求给定二叉树的最大深度，

深度是指树的根节点到任一叶子节点路径上节点的数量。

最大深度是所有叶子节点的深度的最大值。

（注：叶子节点是指没有子节点的节点。）

数据范围：0≤n≤100000，树上每个节点的val满足∣val∣≤100 要求：空间复杂度O(1), 时间复杂度O(n)

解法1 递归

递归解题三步骤：终止条件、返回值、本级任务。

终止条件：根节点为空
返回值：当前层的深度
本级任务：求当前层的最大深度

import java.util.*;

public class Solution {

    public int maxDepth (TreeNode root) {
        if(root == null)
            return 0;
        // 求两个数的较大值
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

解法2 层序遍历

import java.util.*;

public class Solution {

    public int maxDepth (TreeNode root) {
        if(root == null)
            return 0;
        Queue<TreeNode> q = new ArrayDeque<TreeNode>();
        q.add(root);
        int depth = 0;
        while(!q.isEmpty()) {
            int n = q.size();
            for(int i = 0; i < n; i++) {
                TreeNode node = q.poll();
                if(node.left != null)
                    q.add(node.left);
                if(node.right != null)
                    q.add(node.right);
            }
            depth++;
        }
        return depth;
    }
}

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

题目

给定一个二叉树root和一个值 sum，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。

1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点

2.叶子节点是指没有子节点的节点

3.路径只能从父节点到子节点，不能从子节点到父节点

4.总节点数目为n

例如：给出如下的二叉树，sum=22，

返回true，因为存在一条路径 5→4→11→2的节点值之和为 22

数据范围：

1.树上的节点数满足0≤n≤10000

2.每个节点的值都满足∣val∣≤1000

要求：空间复杂度O(n) ，时间复杂度O(n)

进阶：空间复杂度O(树的高度)，时间复杂度O(n)

示例：

示例1：
输入：{5,4,8,1,11,#,9,#,#,2,7},22
返回值：true
示例2：
输入：{1,2},0
返回值：false
示例3：
输入：{1,2},3
返回值：true
示例4：
输入：{},0
返回值：false

解法1 递归

递归解题三步骤：终止条件、返回值、本级任务。

终止条件：找到一条路径和为sum，或根节点为空(没有找到和为sum的路径)。

import java.util.*;

public class Solution {

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

解法2 栈、深度优先

图示：

alt

import java.util.*;

public class Solution {

    public boolean hasPathSum (TreeNode root, int sum) {
        if(root == null)
            return false;
        // stk1储存树的节点
        Stack<TreeNode> stk1 = new Stack<TreeNode>();
        // stk2储存到当前节点的加和
        Stack<Integer> stk2 = new Stack<Integer>();
        stk1.push(root);
        stk2.push(root.val);
        while(!stk1.empty()) {
            TreeNode node = stk1.pop();
            int n = stk2.pop();
            if(node.left == null && node.right == null && n == sum)
                return true;
            if(node.left != null) {
                stk1.push(node.left);
                stk2.push(n + node.left.val);
            }
            if(node.right != null) {
                stk1.push(node.right);
                stk2.push(n + node.right.val);
            }
        }
        return false;
    }
}

BM30 二叉搜索树与双向链表(中等) ？？没看懂

题目

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示

数据范围：输入二叉树的节点数0≤n≤1000，二叉树中每个节点的值0≤val≤1000 要求：空间复杂度O(1)（即在原树上操作），时间复杂度O(n)

注意:

1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继

2.返回链表中的第一个节点的指针

3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构

4.你不用输出双向链表，程序会根据你的返回值自动打印输出

输入描述：

二叉树的根节点

返回值描述：

双向链表的其中一个头节点。

示例：

示例1：
输入：{10,6,14,4,8,12,16}
返回值：From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;
说明：输入题面图中二叉树，输出的时候将双向链表的头节点返回即可。
示例2：
输入：{5,4,#,3,#,2,#,1}
返回值：From left to right are:1,2,3,4,5;From right to left are:5,4,3,2,1;
说明：
                    5
                  /
                4
              /
            3
          /
        2
      /
    1
树的形状如上图  

解法1 递归中序遍历

递归解题三步骤：终止条件、返回值、本级任务。

终止条件：
返回值：
本级任务：

public class Solution {
    // 头节点(返回值)
    public TreeNode head = null;
    // 中序遍历当前值的上一位
    public TreeNode pre = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null)
            return null;
        // 递归找到最小值
        Convert(pRootOfTree.left);
        // 初始化
        if(pre == null){
            head = pRootOfTree;
            pre = pRootOfTree;
        }
        else{
            // 已经处理完左边了，准备处理上一节点的右节点
            pre.right = pRootOfTree;
            pRootOfTree.left = pre;
            pre = pRootOfTree;
        }
        Convert(pRootOfTree.right);
        return head;
    }
}

解法2 栈

BM31 对称的二叉树(简单)

题目

题目链接

给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）例如：下面这棵二叉树是对称的下面这棵二叉树不对称。

数据范围：节点数满足0≤n≤1000，节点上的值满足∣val∣≤1000

要求：空间复杂度 O(n)，时间复杂度O(n)

备注：

你可以用递归和迭代两种方法解决这个问题

示例：

示例1：
输入：{1,2,2,3,4,4,3}
返回值：true
示例2：
输入：{8,6,9,5,7,7,5}
返回值：false

解法1 递归

递归解题三步骤：终止条件、返回值、本级任务。

终止条件：当进入子问题的两个节点都为空，说明都到了叶子节点，且是同步的，因此结束本次子问题，返回true；当进入子问题的两个节点只有一个为空，或是元素值不相等，说明这里的对称不匹配，同样结束本次子问题，返回false。
返回值：每一级将子问题是否匹配的结果往上传递。
本级任务：每个子问题，需要按照上述思路，“根左右”走左边的时候“根右左”走右边，“根左右”走右边的时候“根右左”走左边，一起进入子问题，需要两边都是匹配才能对称。

public class Solution {

    boolean recursion(TreeNode root1, TreeNode root2){
        // 都为空
        if(root1 == null && root2 == null)
            return true;
        // 其中一个为空，或者都非空且值不相等
        if(root1 == null || root2 == null || root1.val != root2.val)
            return false;
        return recursion(root1.left, root2.right) && recursion(root1.right, root2.left);
    }

    boolean isSymmetrical(TreeNode pRoot) {
        return recursion(pRoot, pRoot);
    }
}

解法2 迭代、层序遍历

边迭代边检查是否对称。

import java.util.*;

public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        if(pRoot == null)
            return true;
        // 一定记住初始化队列的时候右边是LinkedList或者ArrayDeque，不是Queue
        Queue<TreeNode> q1 = new LinkedList<TreeNode>();
        Queue<TreeNode> q2 = new LinkedList<TreeNode>();
        q1.add(pRoot.left);
        q2.add(pRoot.right);
        while(!q1.isEmpty() && !q2.isEmpty()){
            TreeNode left = q1.poll();
            TreeNode right = q2.poll();
            // 都为空
            if(left == null && right == null)
                continue;
            // 其中一个为空，或者都非空且值不相等
            if(left == null || right == null || left.val != right.val)
                return false;
            q1.add(left.left);
            q1.add(left.right);
            q2.add(right.right);
            q2.add(right.left);
        }
        return true;
    }
}

附错误解法：左子树按左-根-右遍历，右子树按右-根-左遍历，比较遍历结果。

import java.util.*;

public class Solution {

    void normalOrder(List list, TreeNode root) {
        if(root == null)
            return ;
        normalOrder(list, root.left);
        list.add(root.val);
        normalOrder(list, root.right);
    }

    void reverseOrder(List list, TreeNode root){
        if(root == null)
            return ;        
        reverseOrder(list, root.right);
        list.add(root.val);
        reverseOrder(list, root.left);
    }

    boolean isSymmetrical(TreeNode pRoot) {
        if(pRoot == null)
            return true;
        ArrayList<Integer> list1 = new ArrayList();
        ArrayList<Integer> list2 = new ArrayList();
        normalOrder(list1, pRoot.left);
        reverseOrder(list2, pRoot.right);
        if(list1.size() != list2.size())
            return false;
        for(int i = 0; i < list1.size(); i++){
            if(list1.get(i) != list2.get(i))
                return false;
        }
        return true;
        
    }
}

错误之处在于：一次遍历的结果不能确定树的结构，总有测试用例能满足遍历结果相同，但实际上树的结构并不相同。所以应该边迭代边检查。

BM32 合并二叉树(简单)

题目

题目链接

已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。例如：两颗二叉树是: Tree 1

Tree 2 合并后的树为

数据范围：树上节点数量满足0≤n≤500，树上节点的值一定在32位整型范围内。

进阶：空间复杂度 O(1) ，时间复杂度O(n)

示例：

示例1：
输入：{1,3,2,5},{2,1,3,#,4,#,7}
返回值：{3,4,5,5,4,#,7}
说明：如题面图 
示例2：
输入：{1},{}
返回值：{1}

解法递归

递归前序遍历。

终止条件：至少一个树为空。
返回值：父节点。
本级任务：将两个树的当前节点相加。

import java.util.*;

public class Solution {
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        if(t1 == null)
            return t2;
        if(t2 == null)
            return t1;
        TreeNode head = new TreeNode(t1.val + t2.val);
        head.left = mergeTrees(t1.left, t2.left);
        head.right = mergeTrees(t1.right, t2.right);
        return head;
    }
}

BM33 二叉树的镜像(简单)

题目

题目链接

操作给定的二叉树，将其变换为源二叉树的镜像。

数据范围：二叉树的节点数0≤n≤1000 ，二叉树每个节点的值0≤val≤1000

要求：空间复杂度O(n) 。本题也有原地操作，即空间复杂度O(1) 的解法，时间复杂度O(n)

比如：

源二叉树

镜像二叉树

示例：

示例1：
输入：{8,6,10,5,7,9,11}
返回值：{8,10,6,11,9,7,5}
说明：如题面所示 
示例2：
输入：{}
返回值：{}

解法1 递归

终止条件：树为空。
返回值：根节点（父节点）。
本级任务：翻转左子树和右子树。

import java.util.*;

public class Solution {
    public TreeNode Mirror (TreeNode pRoot) {
        if(pRoot == null)
            return pRoot;
        TreeNode left = Mirror(pRoot.left);
        TreeNode right = Mirror(pRoot.right);
        pRoot.left = right;
        pRoot.right = left;
        return pRoot;
    }
}

解法2 栈

import java.util.*;

public class Solution {
    public TreeNode Mirror (TreeNode pRoot) {
        if(pRoot == null)
            return pRoot;
        Stack<TreeNode> stk = new Stack<TreeNode>();
        stk.push(pRoot);
        while(!stk.isEmpty()) {
            TreeNode node = stk.pop();
            // 子节点进栈
            if(node.left != null)
                stk.push(node.left);
            if(node.right != null)
                stk.push(node.right);
            // 交换左右子树
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
        }
        return pRoot;
    }
}

BM34 判断是不是二叉搜索树(中等)

题目

题目链接

给定一个二叉树根节点，请你判断这棵树是不是二叉搜索树。

二叉搜索树满足每个节点的左子树上的所有节点均小于当前节点且右子树上的所有节点均大于当前节点。

例：

图1

图2

数据范围：节点数量满足1≤n≤10^4^ ，节点上的值满足 −2^31^≤ val ≤2^31^−1

示例：

示例1：
输入：{1,2,3}
返回值：false
说明：如题面图1 
示例2：
输入：{2,1,3}
返回值：true
说明：如题面图2 

解法1 递归

step 1：首先递归到最左，初始化maxLeft与pre。

step 2：然后往后遍历整棵树，依次连接pre与当前节点，并更新pre。

step 3：左子树如果不是二叉搜索树返回false。

step 4：判断当前节点是不是小于前置节点，更新前置节点。

step 5：最后由右子树的后面节点决定。

终止条件：根节点为空
返回值：boolean
本级任务：判断根节点的值是否大于左子节点的值

import java.util.*;

public class Solution {
    // 注意最小整型数的写法
    int pre = Integer.MIN_VALUE;
    //中序遍历
    public boolean isValidBST (TreeNode root) { 
        if (root == null)
            return true;
        //先进入左子树
        if(!isValidBST(root.left)) 
            return false;
        if(root.val < pre)
            return false;
        //更新最值
        pre = root.val;
        //再进入右子树
        return isValidBST(root.right); 
    }
}

解法2 中序遍历、栈

二叉搜索树的中序遍历结果是升序数组。如果存在降序，则不是二叉搜索树。

import java.util.*;

public class Solution {
    public boolean isValidBST (TreeNode root) {
        if(root == null)
            return true;
        ArrayList<Integer> arr = new ArrayList<Integer>();
        Stack<TreeNode> stk = new Stack<TreeNode>();
        TreeNode cur = root;
        while(cur != null || !stk.isEmpty()) {
            // 直到没有左节点
            while(cur != null) {
                stk.push(cur);
                cur = cur.left;
            }
            cur = stk.pop();
            // 访问节点
            arr.add(cur.val);
            // 进入右边
            cur = cur.right;
        }
        // 遍历中序结果，如果有降序，则不是搜索树
        for(int i = 1; i < arr.size(); i++) {
            if(arr.get(i - 1) > arr.get(i))
                return false;
        }
        return true;
    }
}

BM35 判断是不是完全二叉树(中等)

题目

题目链接

给定一个二叉树，确定他是否是一个完全二叉树。

完全二叉树的定义：若二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。（第 h 层可能包含 [1~2h] 个节点）

数据范围：节点数满足1≤n≤100

样例图1：

样例图2：

样例图3：

示例：

示例1：
输入：{1,2,3,4,5,6}
返回值：true
示例2：
输入：{1,2,3,4,5,6,7}
返回值：true
示例3：
输入：{1,2,3,4,5,#,6}
返回值：false

解法层序遍历、队列

如果遇到某个节点为空，进行标记，代表到了完全二叉树的最下层，若是后续还有访问，则说明提前出现了叶子节点，不符合完全二叉树的性质。

import java.util.*;

public class Solution {
    public boolean isCompleteTree (TreeNode root) {
        if(root == null)
            return true;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        boolean complete = false;
        TreeNode cur;
        while(!q.isEmpty()) {
            cur = q.poll();
            if(cur == null) {
                complete = true;
                continue;
            }
            if(complete)
                return false;
            q.add(cur.left);
            q.add(cur.right);
        }
        return true;
    }
}

BM36 判断是不是平衡二叉树(简单)

题目

题目链接

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

样例解释：

样例二叉树如图，为一颗平衡二叉树

注：我们约定空树是平衡二叉树。

数据范围：n≤100,树上节点的val值满足 0≤n≤1000

要求：空间复杂度O(1)，时间复杂度 O(n)

注：这个复杂度要求明显不合理，牛客还有一小部分复杂度要求不合理的，不超时就行

输入描述：

输入一棵二叉树的根节点

返回值描述：

输出一个布尔类型的值

示例：

示例1：
输入：{1,2,3,4,5,6,7}
返回值：true
示例2：
输入：{}
返回值：true

解法1 自顶向下

public class Solution {
    // 递归求树的深度
    public int depth(TreeNode root) {
        if(root == null)
            return 0;
        int left = depth(root.left);
        int right = depth(root.right);
        return (left > right) ? left + 1 : right + 1;
    }

    // 递归判断是否为平衡二叉树
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null)
            return true;
        int left = depth(root.left);
        int right = depth(root.right);
        if(left - right > 1 || left - right < -1) {
            return false;
        }
        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }
}

时间复杂度：O(n^2^)，其中n为二叉树的节点数，第一个递归遍历二叉树所有节点，第二个递归查找深度最坏情况下（二叉树退化为链表）需要遍历二叉树所有节点。
空间复杂度：O(n)，递归栈最大深度为n。

解法2 自底向上

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null)
            return true;
        return getDepth(root) != -1;
    }

    // 求左右子树的深度
    // 非负数是平衡二叉树的深度，-1不是平衡二叉树
    public int getDepth(TreeNode root) {
        if(root == null)
            return 0;
        int left = getDepth(root.left);
        if(left < 0)
            return -1;
        int right = getDepth(root.right);
        if(right < 0)
            return -1;
        // 左右子树的高度差大于1，不是平衡二叉树，返回-1；
        // 左右子树的高度差不大于1，是平衡二叉树，返回左右子树更大的深度+1
        return Math.abs(left - right) > 1 ? -1 : Math.max(left, right) + 1;
    }
}

时间复杂度：O(n)，其中n为树的节点数，一次递归遍历二叉树所有节点。
空间复杂度：O(n)，最坏情况下递归栈的深度为n。

BM37 二叉搜索树的最近公共祖先(简单)

题目

题目链接

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

1.对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先.

2.二叉搜索树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值

3.所有节点的值都是唯一的。

4.p、q 为不同节点且均存在于给定的二叉搜索树中。

数据范围:

3<=节点总数<=10000

0<=节点值<=10000

如果给定以下搜索二叉树: {7,1,12,0,4,11,14,#,#,3,5}，如下图:

示例：

示例1：
输入：{7,1,12,0,4,11,14,#,#,3,5},1,12
返回值：7
说明：节点1 和 节点12的最近公共祖先是7  
示例2：
输入：{7,1,12,0,4,11,14,#,#,3,5},12,11
返回值：12
说明：因为一个节点也可以是它自己的祖先.所以输出12  

解法递归

import java.util.*;
public class Solution {
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        //空树找不到公共祖先
        if(root == null) 
            return -1;
        //pq在该节点两边说明这就是最近公共祖先
        if((p >= root.val && q <= root.val) || (p <= root.val && q >= root.val)) 
            return root.val;
        //pq都在该节点的左边
        else if(p <= root.val && q <= root.val) 
            //进入左子树
            return lowestCommonAncestor(root.left, p, q); 
        //pq都在该节点的右边
        else 
            //进入右子树
            return lowestCommonAncestor(root.right, p, q); 
    }
}

BM38 在二叉树中找到两个节点的最近公共祖先(中等)

题目

题目链接

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

数据范围：树上节点数满足1≤n≤105 , 节点值val满足区间 [0,n)

要求：时间复杂度O(n)

注：本题保证二叉树中每个节点的val值均不相同。

如当输入{3,5,1,6,2,0,8,#,#,7,4},5,1时，二叉树{3,5,1,6,2,0,8,#,#,7,4}如下图所示：

所以节点值为5和节点值为1的节点的最近公共祖先节点的节点值为3，所以对应的输出为3。

节点本身可以视为自己的祖先。

示例：

示例1：
输入：{3,5,1,6,2,0,8,#,#,7,4},5,1
返回值：3
示例2：
输入：{3,5,1,6,2,0,8,#,#,7,4},2,7
返回值：2

解法1 递归

终止条件：当前节点的值等于其中一个目标值，或者没有找到目标值；
返回值：找到节点，返回节点值；没有找到，返回-1；
本级任务：分别在左子树、右子树中寻找目标值的公共节点。

import java.util.*;
public class Solution {
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        //该子树没找到，返回-1
        if(root == null) 
            return -1;
        //该节点是其中某一个节点
        if(root.val == o1 || root.val == o2) 
            return root.val;
        //左子树寻找公共祖先
        int left = lowestCommonAncestor(root.left, o1, o2); 
        //右子树寻找公共祖先
        int right = lowestCommonAncestor(root.right, o1, o2); 
        //左子树为没找到，则在右子树中
        if(left == -1) 
            return right;
        //右子树没找到，则在左子树中
        if(right == -1) 
            return left;
        //否则是当前节点
        return root.val; 
    }
}

解法2 路径比较、dfs

找到到两个节点的路径，找到两条路径最后一个相同节点，即为最近公共祖先。

import java.util.*;

public class Solution {
	// 记录是否找到
    boolean flag = false;
    // 求根节点到目标节点的路径，储存在path中
    public void dfs(TreeNode root, ArrayList<Integer> path, int o) {
        if(flag || root == null)
            return ;
        path.add(root.val);
        if(root.val == o) {
            flag = true;
            return ;
        }
        dfs(root.left, path, o);
        dfs(root.right, path, o);
        if(flag)
            return ;
        // 该条路径没找到，回溯，删掉这条路径的最后一个节点，从倒数第二个节点继续找
        path.remove(path.size() - 1);
    }

    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        ArrayList<Integer> path1 = new ArrayList<Integer>();
        ArrayList<Integer> path2 = new ArrayList<Integer>();
        dfs(root, path1, o1);
        flag = false;
        dfs(root, path2, o2);
        int res = 0;
        // 两条路径的开头可能有相同的节点，要找到最后一个相同节点，即为最近公共祖先
        for(int i = 0; i < path1.size() && i < path2.size(); i++) {
            int x = path1.get(i);
            int y = path2.get(i);
            if(x == y)
                res = x;
            else
                break;
        }
        return res;
    }
}

BM39 序列化二叉树(较难)

题目

题目链接

请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。

二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过某种符号表示空节点（#）

二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

例如，可以根据层序遍历的方案序列化，如下图:

层序序列化(即用函数Serialize转化)如上的二叉树转为”{1,2,3,#,#,6,7}”，再能够调用反序列化(Deserialize)将”{1,2,3,#,#,6,7}”构造成如上的二叉树。

当然你也可以根据满二叉树结点位置的标号规律来序列化，还可以根据先序遍历和中序遍历的结果来序列化。不对序列化之后的字符串进行约束，所以欢迎各种奇思妙想。

数据范围：节点数n≤100，树上每个节点的值满足0≤val≤150

要求：序列化和反序列化都是空间复杂度O(n)，时间复杂度O(n)

示例：

示例1：
输入：{1,2,3,#,#,6,7}
返回值：{1,2,3,#,#,6,7}
说明：如题面图 
示例2：
输入：{8,6,10,5,7,9,11}
返回值：{8,6,10,5,7,9,11}

解法层序遍历

import java.util.*;

public class Solution {
    int INF = 0x3f3f3f3f;
    TreeNode emptyNode = new TreeNode(INF);
    String Serialize(TreeNode root) {
        if (root == null) return "";
		// 构建字符串StringBuilder类
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            // 给StringBuilder类的变量增加字符的方法append()
            sb.append(node.val + "_");
            if (!node.equals(emptyNode)) {
                q.add(node.left != null ? node.left : emptyNode);
                q.add(node.right != null ? node.right : emptyNode);
            }
        }
        return sb.toString();
    }
    TreeNode Deserialize(String str) {
        // 判断字符串是否为空
        if (str.equals("")) return null;

        // 将字符串按字符"_"划分为字符串数组
        String[] s = str.split("_");
        // 数组的length后不需要加括号
        int len = s.length;
        TreeNode root = new TreeNode(Integer.parseInt(s[0]));
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        for (int i = 1; i < len - 1; i += 2) {
            TreeNode node = q.poll();
            // 方法parseInt()将字符转化为Integer
            int a = Integer.parseInt(s[i]), b = Integer.parseInt(s[i + 1]);
            if (a != INF) {
                node.left = new TreeNode(a);
                q.add(node.left);
            }
            if (b != INF) {
                node.right = new TreeNode(b);
                q.add(node.right);
            }
        }
        return root;
    }
}

时间复杂度 O(n)

空间复杂度 O(n)

BM40 重建二叉树(中等)

题目

题目链接

给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。

提示:

1.vin.length == pre.length

2.pre 和 vin 均无重复元素

3.vin出现的元素均出现在 pre里

4.只需要返回根结点，系统会自动输出整颗树做答案对比

数据范围：n≤2000，节点的值 −10000≤val≤10000

要求：空间复杂度 O(n)，时间复杂度 O(n)

示例：

示例1：
输入：[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]
返回值：{1,2,3,4,#,5,6,#,7,#,#,8}
说明：返回根节点，系统会输出整颗二叉树对比结果，重建结果如题面图示 
示例2：
输入：[1],[1]
返回值：{1}
示例3：
输入：[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
返回值：{1,2,5,3,4,6,7}

解法递归

对于二叉树的前序遍历，我们知道序列的第一个元素必定是根节点的值，因为序列没有重复的元素，因此中序遍历中可以找到相同的这个元素，而我们又知道中序遍历中根节点将二叉树分成了左右子树两个部分，如下图所示：

图片说明

从已知数组中截取一段生成新数组：Arrays.copyOfRange()方法，第一个参数为数组，第二个和第三个参数为开始和结束的下标。

import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        int n = pre.length;
        int m = vin.length;
        //每个遍历都不能为0
        if(n == 0 || m == 0) 
            return null;
        //构建根节点
        TreeNode root = new TreeNode(pre[0]);
        for(int i = 0; i < vin.length; i++){
            //找到中序遍历中的前序第一个元素
            if(pre[0] == vin[i]){ 
                //构建左子树
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), 
                                                  Arrays.copyOfRange(vin, 0, i)); 
                //构建右子树
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), 
                                                   Arrays.copyOfRange(vin, i + 1, vin.length));
                break;
            }
        }
        return root;
    }
}

BM41 输出二叉树的右视图(中等)

题目

题目链接

请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图

数据范围：0≤n≤10000 要求：空间复杂度 O(n)，时间复杂度 O(n)

如输入[1,2,4,5,3],[4,2,5,1,3]时，通过前序遍历的结果[1,2,4,5,3]和中序遍历的结果[4,2,5,1,3]可重建出以下二叉树：

所以对应的输出为[1,3,5]。

示例：

输入：[1,2,4,5,3],[4,2,5,1,3]
返回值：[1,3,5]

备注：

二叉树每个节点的值在区间[1,10000]内，且保证每个节点的值互不相同。

解法递归、哈希

解法链接

import java.util.*;

public class Solution {

    // ans为结果Map，ans(m, n)的参数为第m层的最右节点值n
    private HashMap<Integer, Integer> ans = new HashMap<>();
    // inOrderMap为中序遍历Map，ans(m, n)的参数为中序遍历的下标n和当前节点值m
    private HashMap<Integer, Integer> inOrderMap = new HashMap<>();

    public int[] solve (int[] preOrder, int[] inOrder) {
        // 中序遍历放进HashMap，便于寻找根节点值对应的中序遍历下标
        for (int i = 0; i < inOrder.length; i++) {
            inOrderMap.put(inOrder[i], i);
        }
        build(preOrder, inOrder, 0, inOrder.length - 1, 0);
        // 处理输出，将HashMap值放进int[]中作为返回值
        int[] temp = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            temp[i] = ans.get(i);
        }
        return temp;
    }

    // 树的深度
    private int depth = 0;
    // num为前序遍历的下标值
    private int num = 0;
    // 参数分别为：前序、中序、开始下标、结尾下标、树深度
    public void build(int[] preOrder, int[] inOrder, int start, int end,
                      int depth) {
        // 递归终止条件
        if (start > end)
            return ;
        // 寻找根节点
        int index = inOrderMap.get(preOrder[num++]);
        // 左子树
        build(preOrder, inOrder, start, index - 1, depth + 1);
        // 右子树
        build(preOrder, inOrder, index + 1, end, depth + 1);
        // 第depth层的最右节点为inOrder[index]，左子树的最右节点会被右子树的最右节点覆盖掉
        ans.put(depth, inOrder[index]);
    }
}

总结

普通遍历用栈，层序遍历用队列。

递归在树的题目中很常用，往往左子树一个递归，右子树一个递归。

递归解题三步骤：终止条件、返回值、本级任务。

树的递归方法的参数有：

遍历数组（前序中序后序层序）、数组下标
根节点
树的深度

目录

二叉树（牛客）

BM23 二叉树的前序遍历(简单)

题目

解法1 递归

解法2 栈

BM25 二叉树的后序遍历(简单)

解法1 递归

解法2 栈

BM24 二叉树的中序遍历(中等)

题目

解法1 递归

解法2 栈

BM26 求二叉树的层序遍历(简单)

题目

解法1 队列

解法2 递归

BM27 按之字形顺序打印二叉树(中等)

题目

解法1 队列

解法2 栈

BM28 二叉树的最大深度(简单)

题目

解法1 递归

解法2 层序遍历

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

题目

解法1 递归

解法2 栈、深度优先

BM30 二叉搜索树与双向链表(中等) ？？没看懂

题目

解法1 递归中序遍历

解法2 栈

BM31 对称的二叉树(简单)

题目

解法1 递归

解法2 迭代、层序遍历

BM32 合并二叉树(简单)

题目

解法 递归

BM33 二叉树的镜像(简单)

题目

解法1 递归

解法2 栈

BM34 判断是不是二叉搜索树(中等)

题目

解法1 递归

解法2 中序遍历、栈

BM35 判断是不是完全二叉树(中等)

题目

解法 层序遍历、队列

BM36 判断是不是平衡二叉树(简单)

题目

解法1 自顶向下

解法2 自底向上

BM37 二叉搜索树的最近公共祖先(简单)

题目

解法 递归

BM38 在二叉树中找到两个节点的最近公共祖先(中等)

题目

解法1 递归

解法2 路径比较、dfs

BM39 序列化二叉树(较难)

题目

解法 层序遍历

BM40 重建二叉树(中等)

题目

解法 递归

BM41 输出二叉树的右视图(中等)

题目

解法 递归、哈希

总结

解法递归

解法层序遍历、队列

解法递归

解法层序遍历

解法递归

解法递归、哈希