vlambda博客
学习文章列表

前言

新文章还没有准备好，所以先来一篇算法咯，嘿嘿，新文章周一见。

今天继续说说二叉树的算法。

不知道大家有没有发现，二叉树的很多问题都会涉及到递归算法，今天就来小结一下。

小结

      1 
    /   \
   2     3  
  / \   / \
 4   5  6  7 

二叉树的遍历，一共有三种：前序、中序、后序。

• 前序。代表每个树都会按照中间节点、左节点、右节点的方式排序，上述例子的前序排列就是： 1、2、4、     5、     3、6、7
• 中序。代表每个树都会按照左节点、中间节点、右节点的方式排序，上述例子的中序排列就是： 4、2、5、     1、     6、3、7
• 后序。代表每个树都会按照左节点、右节点、中间节点的方式排序，上述例子的后序排列就是： 4、5、2、   6、7、3、     1

通过三种遍历情况，我们可以发现的共通点是：都是先左节点，后右节点，只是中间节点的位置不同。
所以综合一下，可以得出一种通用的二叉树遍历方法，是一种递归算法：

//二叉树的递归
void traverse(TreeNode root) {
 if (root==null) return
    traverse(root.left)
    traverse(root.right)
}

但是、这个递归跟我们的遍历方法有什么关系呢，也没看到具体的前序、中序、后序啊？

递归的精妙之处就在于，递和归是两个过程，而在不同的过程进行处理就会有不同的结果。

我们试着在递的过程中加入打印：

//二叉树的递归
void traverse(TreeNode root) {
 if (root==null) return

 // 前序遍历点
    System.out.println(root.val)

    traverse(root.left)
    traverse(root.right)
}

在方法开始进行节点打印，那么就会一路从左边打印下来：

• traverse(1),traverse(2),traverse(4)
• traverse(5)
• traverse(3),traverse(6),traverse(7)

同样，在递和归直接打印节点就是中序遍历，在归阶段打印节点就是后序遍历，最后得出二叉树遍历的总结递归方法：

//二叉树的递归
void traverse(TreeNode root) {
    // 前序遍历点
    System.out.println(root.val)

    traverse(root.left)

    // 中序遍历点
    System.out.println(root.val)

    traverse(root.right)

    // 后序遍历点
    System.out.println(root.val)
}

以后遇到二叉树的问题就可以把这个递归方法作为基础进行延伸。

题目

再来个题目进行巩固：二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：

输入：root = [1,2,5,3,4,null,6] 输出：[1,null,2,null,3,null,4,null,5,null,6]

题解

题目已经给出了链表的顺序就是先序遍历，所以我们可以先对二叉树进行先序遍历，保存到集合，然后再针对集合每个值的左右节点进行赋值（left->null, right-> 下个节点）：

class Solution {
    public void flatten(TreeNode root) {
        List<TreeNode> list = new ArrayList<TreeNode>();
        preorderTraversal(root, list);
        int size = list.size();
        for (int i = 1; i < size; i++) {
            TreeNode prev = list.get(i - 1), curr = list.get(i);
            prev.left = null;
            prev.right = curr;
        }
    }

    public void preorderTraversal(TreeNode root, List<TreeNode> list) {
        if (root != null) {
            list.add(root);
            preorderTraversal(root.left, list);
            preorderTraversal(root.right, list);
        }
    }
}

再结合我们刚才的小结，通过递归方法就可以完成先序遍历，然后再一个个进行前后指针赋值就可以了。

这样看是不是挺简单的？

复杂度

时间复杂度：O(n) 空间复杂度：O(n)

题解2

还有没有其他的解法呢？

我们在回顾下前序的规律：

中间节点、左节点、右节点

所以对于某个节点来说，其右子树肯定在左子树的后面，而左子树中的最后一个节点就是左子树中最右边的节点，这个节点也就是右子树的前驱节点，来个图：

      1 
    /   \
   2     3  
  / \     \
 4   5     7 

对于根节点1，3子树的前驱节点就是2子树最右边的节点，也就是5。

所以我们可以把3子树作为5这个链表节点的下一个指针指向。

这样一个个节点处理完之后，链表结构就出来了，比如上述的例子：

• 第一步：把5作为3子树的前驱节点。
• 第二步：把2子树作为1的右子树

就变成了：

  1     
   \   
   2    
  / \  
 4   5 
     \ 
      3    
      \  
       7

• 第三步：把4作为5子树的前驱节点

继续遍历，直到最后一个节点7，都没有左子树了，完成解法。

贴上代码：

class Solution {
    public void flatten(TreeNode root) {
        TreeNode curr = root;
        while (curr != null) {
         //判断还有没有右子树
            if (curr.left != null) {
             //判断还有没有左子树
                TreeNode next = curr.left;
                TreeNode predecessor = next;
                while (predecessor.right != null) {
                 //找到左子树中最右边的节点
                    predecessor = predecessor.right;
                }
                //作为前驱节点
                predecessor.right = curr.right;
                //重新赋值右子树
                curr.left = null;
                curr.right = next;
            }
            //继续遍历
            curr = curr.right;
        }
    }
}

复杂度

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

参考

https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list

每日一个知识点，建立完整体系架构。