二叉树专题突破-遍历与思路

1. 深入理解前中后序的遍历

首先抛开遍历这种动作,我们从前序位置、中序位置、后序位置这三种位置来进行分析

所谓前序位置,就是在刚进入一个节点(元素)的位置

所谓后序位置,就是在即将离开一个节点(元素)的位置

所谓中序位置,就在处理完一个节点的左子树的元素后的位置

我们可以看出,前/中/后它更多的是描述一种代码执行的时机,那么遍历也就是将相关的代码写在相关的位置,从而达成不同的遍历序列

前序遍历的特点是:根节点的值排在首位,然后接着是左子树的前序遍历结果,最后是右子树的遍历结果

2. 二叉树的解题思路

二叉树题目的递归解法可以分为两种思路

第一种是遍历一遍二叉树得出答案,通常的手段是借助于traverse()和外部指针变量,这种思路可以看做是回溯算法的变种

第二种是分解问题,通过分解问题计算出答案

是否可以通过遍历一遍二叉树来得到答案?如果可以,使用traverse()和外部变量完成遍历
是否可以定义一个递归函数?通过子问题的答案来推导出原问题的答案?如果可以,那么就写出这个递归函数的定义,并充分利用这个函数的返回值

无论使用哪一种思维模式,都需要明确地知道二叉树的每一个节点需要做什么,需要在什么时候做

3.后序位置的特殊之处

前序位置的代码是自顶向下的,而后序位置的代码的执行是自底向上的

这意味着前序位置的代码只能够从函数传参中得到父节点传递过来的数据,而后序位置的代码能够获取除了父节点传递过来的数据,还能得到左右子树计算出来的结果

如果把根节点看作是第一层,如何打印出每一个节点所在的层数?

对于这个问题,我们首先思考的是,这个问题需要左右子树的计算结果作为答案吗?

很显然是不需要的,因此采用前序遍历即可

如何打印出每个节点的左右子树各有多少个节点?

这个问题需要左右子树的计算结果作为答案吗?

很显然需要,因此需要采用后续遍历

一旦你发现题目和子树是相关的,那么大概率就要给函数设置返回值和合理的定义了,然后在后序位置写代码

例题解析

543. 二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树

    1
   / \
  2   3
 / \     
4   5    

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

首先这道题完整的分析一下,先审题,题目要求的是是任意两个结点路径长度中的最大值,要求最大值,又说可以通过根节点,可以不通过根节点,但是我们分析一下,节点路径长度的最大值,必然是左子树的最深叶子节点到根节点所产生的路径长度+右子树的最深叶子节点到根节点所产生的路径长度,注意,我这里说的根节点不是指整颗二叉树的根节点,而是指的是相对于左右子树的根节点

也就是说二叉树上的每一个节点都有可能会产生这个最大路径

那么于是我只要遍历这棵二叉树上的节点,计算他们所可能产生的最大路径和即可,既然是遍历的思路,那么就要定义traverse()和外部变量了,这是前序遍历的思路,具体的代码如下:

public int diameterOfBinaryTree(TreeNode root) {
    traverse(root);
    return res;
}
private int res = 0;
private void traverse(TreeNode root){
    if(root == null){
        return ;
    }
    //仅利用父节点传过来的信息进行计算
    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);
    //取较大值
    res = Math.max(res,leftDepth+rightDepth);
    traverse(root.left);
    traverse(root.right);
}
private int maxDepth(TreeNode root){
    if(root == null){
        return 0;
    }
    int leftMax = maxDepth(root.left);
    int rightMax = maxDepth(root.right);
    return Math.max(leftMax,rightMax)+1;
}

说明:两结点之间的路径长度是以它们之间边的数目表示。这句话很重要,首先我们使用的是maxDepth(root.left),它表示的是从root.left->leave有多少个节点,是不算root节点进去的

因此leftMax + rightMax = 最长路径上的节点数-1,而这个节点数正是边数,因此是没有错的

分析一下算法,首先一个问题是,有没有出现重复计算?

我们发现在前序遍历中,由于每个节点都去计算这个最长路径的长度,这会导致一种情况,底层的节点被遍历多次,但是其实是不必要的

第二个问题,一定要放在前序做吗,如果后序做有什么优点?

首先我们解题的思路是:求解出左右子树的最长路径,那么这就要求我们在计算之前提前处理好左右子树,那么使用后序来做是比较合适的

那么在这里就有一个问题了,定义什么样的函数?函数的返回值是什么合适?

首先需要明确的是我们需要什么?需要的是计算出从当前节点到叶子节点所形成的最大路径长度

这个节点需要干什么?最大路径长度,就是左子树的最大路径长度和右子树的最大路径长度取最大即可

private int res = 0;
public int diameterOfBinaryTree(TreeNode root) {
    maxDepth(root);
    return res;
}

private int maxDepth(TreeNode root){
    if(root == null){
        return 0;
    }
    //后续遍历的位置
    int leftMax = maxDepth(root.left);
    int rightMax = maxDepth(root.right);
    res = Math.max(res,leftMax+rightMax);
    return Math.max(leftMax,rightMax)+1;
}

4. 例题:二叉树的镜像

审题:这道题要求我们将二叉树上的每一个节点的左右节点都互换

第一种思路:采用遍历+外部变量的方式

既然是每一个节点的节点都互换,那么我只要遍历这棵树,交换遍历到的每个节点的左右节点即可

private void traverse(TreeNode root){
      if(root == null){
          return ;
      }
      //交换左右子树,前序操作
      TreeNode temp = root.left;
      root.left = root.right;
      root.right = temp;
      traverse(root.left);
      traverse(root.right);
  }

  public TreeNode mirrorTree(TreeNode root) {
      traverse(root);
      return root;
  }

第二种思路:定义合适的递归函数,分解问题

既然是分解问题,而且要让递归函数自洽,那么就要充分利用题目的条件,题目让我们返回的是翻转后的二叉树的根节点,那么我们分解问题的话,翻转后的二叉树,那么它的左子树肯定也是翻转后的,它的右子树肯定也是翻转后的,他们在翻转之后,控制权才交给当前节点,根节点将他们的位置交换

通过这样的分析,我们就可以很容易地知道,应该采用后续遍历的方式

public TreeNode mirrorTree(TreeNode root) {
    if(root == null){
        return null;
    }
    //反转子树
    TreeNode left = mirrorTree(root.left);
    TreeNode right = mirrorTree(root.right);
    root.left = right;
    root.right = left;
    return root;
}

小技巧:二叉树要善于观察题目给的那个模板函数,如果要使用分解问题的话,那么那个模板函数通常能够给我们以启示

5. 例题:填充节点的右侧指针

116. 填充每个节点的下一个右侧节点指针

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

审题:首先这道题说的是给我一个完美二叉树,这个完美二叉树是一个正三角形,保证了除了最右边的节点的next会指向于null之外,其他节点一定有相邻的节点

这道题如果是让我们连接那些相同父节点的两个子节点,那么就会非常简单

root.left.next = root.right

但是这道题还有个情况,这个情况就是连接那些不是同一个父节点的两个相邻节点。

但是其本质也是在做两个节点的连接操作,因此我们的思路如下:

定义递归函数

void connect(Node leftNode,Node rightNode){
    //函数定义为,将leftNode.next=rightNode
}

那么对于二叉树上的每个节点,都要做这个操作,因此这道题确定为遍历的框架,遍历方式任意

public Node connect(Node root) {
    if(root == null){
        return null;
    }
    connect(root.left,root.right);
    return root;
}
private void connect(Node leftNode,Node rightNode){
    if(leftNode == null || rightNode == null){
        return ;
    }
    leftNode.next = rightNode;
    connect(leftNode.left,leftNode.right);
    connect(leftNode.right,rightNode.left);
    connect(rightNode.left,rightNode.right);

}

class Solution {
    public Node connect(Node root) {
        if(root == null){
            return null;
        }
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            int size = q.size();
            Node pre = null;
            for(int i = 0;i<size;i++){
                Node head = q.poll();
                if(pre != null){
                    pre.next = head;
                }
                pre=head;
                if(head.left != null){
                    q.offer(head.left);
                }
                if(head.right != null){
                    q.offer(head.right);
                }
            }
        }
        return root;
    }
}

以上是层次遍历的解法,其本质也是通过遍历的思路来进行解题,不过是认为解题的思路更加贴近于题目

6.例题:将二叉树展开为链表

审题:首先这道题要求的是将二叉树的结果存储到链表中,但是题目给的返回值是void,这就要求我们必须原地修改二叉树,而前序遍历的特点是根左右,因此最终结果链表肯定就是根->左子树打平后的链表->右子树打平后的链表,那么既然涉及到了左子树/右子树计算后的结果,那么基本就是后序遍历了,而且我们发现可以将当前的root问题分解为左子树的计算结果和右子树的计算结果

那么就可以使用分解问题的思路了

定义递归函数,这里题目给的返回函数的定义是打平以root为根节点的二叉树后所产生的根节点

那么这恰是我们想要的一个定义

定义每个节点需要完成什么动作

首先,每个节点需要完成打平二叉树的这个动作,那么要怎么做呢?

首先是拿到它的被打平后的左右子树,然后将它的左子树设置为null,右子树保持不动,然后将左子树拼接到右子树的最后一个节点即可

public void flatten(TreeNode root) {
    if(root == null){
        return ;
    }
    flatten(root.left);
    flatten(root.right);
    //后序遍历
    TreeNode left = root.left;
    TreeNode right = root.right;
    root.left = null;
    root.right = left;
    TreeNode p = root;
    while(p.right!=null){
        p = p.right;
    }
    p.right = right;
}