二叉树 - Guoziren`s World

剑指offer题目

7 重建二叉树(☆☆)

题目：根据中序序列和先序序列构造一颗二叉树，二叉树结点的值都不相同。

算法步骤：

①判空（数组合法性检查）

②找到根节点的值，构造根节点

③在中序数组中找到根节点的位置，以求出左右子树的长度，并递归调用自己

存在左子树构造左子树，存在右子树构造右子树

注: 这里可以理解为用的先序去构造的这颗树，1个结点的左右子树都为空时，会直接返回这个结点。

看看，不用写，过。

8 二叉树的下一个结点：中序后继(☆☆)

给定一个二叉树，1个树中的结点，每个结点有parent指针

三种情况：

①有右子树：右子树的最左结点。

②没有右子树，是父节点的左孩子：所求即为父节点

③没有右子树，是父节点的右孩子：沿着parent指针向上遍历，直到一个是它父节点的左子结点的结点，如果这个结点存在，这个结点的父节点即为所求，都是右子节点的话，就为Null

④没有右子树，也没有parent，所求为Null

注：记住这4种情况即可，不用过代码。

26 树的子结构(☆☆☆)

树的问题采用递归解法的关键在于：在左右子树各看成一个整体。

分2步：

①第一步在树中查找与根节点一样的结点，树的遍历

②第二步判断树A中以R为根节点的子树是不是和树B具有相同的结构

注 :1. 在面试的时候，我们一定要注意边界条件检查，即检查空指针。如果没有检查并进行相应的处理，程序非常容易崩溃，这是面试时非常忌讳的事情。

2.在写遍历树的代码的时候一定要高度警惕，有没有可能是Null,null怎么处理.

3.double类型的比较要注意。

2020-09-21 12:18:50 注： ***4.当前仅当 A B都不空时才有可能是true ，左子树有了就直接返回，先判断左子树。

5.*** 第2步是判断A中是否包含B ，而力扣572 另一颗树的子树是要求A中有子树和B是一样的。

6.*** 第2步判断，B null就返回true

27 二叉树的镜像()

用递归,没星的直接过

28 对称二叉树(☆☆☆)

什么是对称二叉树：1棵树与他的镜像是一样的。

怎么判断对称二叉树：

先序和对称的先序（先右左）序列是一样的，怎么做：根相同的时候，先序的左孩子和对称先序的右孩子相同 && 先序的右孩子和对称先序的右孩子相同时是对称的。

32 从上到下打印二叉树(☆☆☆)

I:直接层次遍历，非常简单，过。

II：一行一行打印，比较简单，用当前行结点数量和下一行结点数量2个变量控制，简单，过；

剑指 Offer 32 - III. 从上到下打印二叉树 III

之字行打印，一行顺序打印，一行逆序打印。

解：

用1个变量表示当前层数curLevel，初始为1，表示奇数层；
用2个栈分别存顺序和逆序输出的一层的结点,LinkedList实现；
奇数层用顺序栈stack1，顺序输出；偶数层用逆序栈stack2，逆序输出
偶数层从逆序栈stack2取结点，偶数层先压右孩子后压左孩子，压入到顺序栈stack1，

III下一步要快速写出来。

33 二叉搜索树的后序遍历序列(☆☆☆☆)

public boolean verifyPostorder2(int[] postorder,int startIndex,int endIndex)函数返回postorder在指定区间内是否满足二叉搜索树的定义。

算法思路：

最后一个元素为根，确定左子树，都比根小，确定右子树，都比根大。
遍历，当找到比root还大的元素时，确定右子树的区间，右子树应当都比根大，不满足时直接返回fale.
左子树存在时调用自己判断是不是二叉排序树
右子树存在时，调用自己判断是不是二叉排序树
最终返回left && true.

数组为null，或者空树也为二叉排序树。

34 二叉树中和为某一值的路径(☆☆☆)

遍历，当前和。

注：关键的一点在于回到根节点时要删除当前结点，二叉树的遍历好好看看。

36 二叉搜索树与双向链表

37 序列化二叉树

54 二叉树搜索树的第k大结点

55 二叉树的深度

二叉树的遍历

1.非递归先序

//非递归先序遍历
    public void preOrderUnCur(TreeNode root){
        if (root == null){
            System.out.println("这是个空树");
            return;
        }
        Stack stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            System.out.print(node.val + " ");
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        System.out.println("");
    }

以下背诵

根节点入栈
当栈不空的时候，循环
1. 弹出栈顶结点，输出
2. 右孩子不空，右孩子入栈
3. 左孩子不空，左孩子入栈

2.非递归中序

初始遍历结点p作为当前结点指向根。

/**
    * 非递归中序遍历
    * 首先建立一个空栈和1个遍历结点指向根节点。
    * 当栈为空 && 当前结点为null时 才结束循环，否则循环执行下面2句
    * 当前结点为空，从栈中弹出一个变成当前结点打印，并指向右孩子；
    * 当前结点不空，当前结点入栈，当前结点并指向左孩子‘
    * @param root 树根
    */
   public void inOrderUnCur(TreeNode root){
       if (root == null){
           System.out.println("这是个空树");
           return;
       }
       Stack stack = new Stack<>();
       TreeNode p = root;
       while (!stack.isEmpty() || p != null){
           if(p != null){
               stack.push(p);
               p = p.left;
           }else{
               p = stack.pop();
               System.out.print(p.val + " ");
               p = p.right;
           }
       }
       System.out.println("");
   }

3.非递归后序

同先序差不多。

根结点入普通栈
当普通栈不空的时候，循环
1. 弹出一个元素，压入到辅助栈
2. 左孩子不空，左孩子入普通栈
3. 右孩子不空，右孩子入普通栈
循环结束，弹出辅助栈所有元素

//非递归后序遍历(实现输出左右中的顺序)
    public void postOrderUnCur(TreeNode root){
        if (root == null){
            System.out.println("这是个空树");
            return;
        }
        Stack stack = new Stack<>();
        Stack helpStack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            helpStack.push(node);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }

        }
        while (!helpStack.isEmpty()){
            TreeNode node = helpStack.pop();
            System.out.print(node.val + " ");
        }
        System.out.println();
    }

4.T32 层次遍历二叉树

通过具体的例子（画个表格逐步分析）找出其中的规律并想到基于队列的算法，是解决这个问题的关键所在。

扩展

还要掌握分行打印(字节跳动)
- 简单，增加2个变量，当前层结点数量初始为1，下一层结点数量初始为0
还要掌握之字形打印
- 分析知道用单个队列，不加其他额外操作不行（保证结点只遍历1次）
- 分析知道只用单个栈也不行
- 要用2个栈,1个栈用于暂存顺序输出的结点，1个栈用于逆序输出的结点，分奇偶层存入不同的stack;
  
  同时分奇偶层去取出结点(有点难度的)
序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。

面试题54:二叉搜索树的第k大结点

利用中序遍历，easy
- 定一个成员变量，递增直到k
- 也可以不用定义成员变量，传参的时候，k–,直到1时就是所求结点

int count = int count = 0;
    TreeNode KthNode(TreeNode pRoot, int k){
        TreeNode result = null;
        if (pRoot == null || k == 0){
            return null;
        }
        result =  KthNode(pRoot.left,k);
        count++;
        if (count == k){
            result = pRoot;
        }
        if (result == null){
            result = KthNode(pRoot.right,k);
        }
        return result;
    }

面试题55：二叉树的深度

题目一：二叉树的深度

递归

题目二：判断是否是平衡二叉树

后序遍历的递归形式

面试题37：二叉树的序列化

1，2，#，#，3，4，#，#，5，#，#，

先序

序列化：

采用递归先序，当前结点为null时，返回null结点标记$,
访问根
递归访问左右子树（函数返回以当前结点为根序列化后的结果）
根 + 左子树序列化的结果 + 右子树序列化的结果

反序列化：

eg: 1，2，#，#，3，4，#，#，5，#，#，这样一棵树。

任然是递归去构造
将参数data split(“,”)成字符串数组，并按入队的顺序(先序遍历的顺序)加入到队列中
- 队列中弹出1个(取出队头)，是空标记(比如”null”)，则returnnull
否则以当前value 构造TreeNode结点
- 根节点左孩子 = 递归调用的返回值，参数为当前队列
- 根节点右孩子 = 递归调用的返回值，参数为当前队列

剑指offer leetcode

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

链表栈队列上一篇

递归下一篇