本文共 1651 字，大约阅读时间需要 5 分钟。

链接：

大意：

给定一棵二叉树的根节点root，使用原地算法（即空间复杂度为O（1））将该二叉树展平为另一类二叉树，展平方式为按照原二叉树的先序遍历序列构造（实际不能重新构造，因为空间复杂度为O（1））树节点，使得每个父节点都只有右孩子。例子：

思路：

递归。首先看看例子有什么特征 ：

• 2，3，4为1的左子树；5，6为1的右子树。对于根节点1，在展平的树中，2->3->4为1的左子树展平形式；5->6为1的右子树展平形式。
• 现在看看怎么把树根节点1与其左子树的展平形式2->3->4以及右子树5->6连接起来。发现1是连接的左子树展平形式的头结点（此时先把展平形式看成一个链表形式），之后左子树展平形式的尾节点连接右子树展平形式的头结点
• 正因为这种关系，所以可以使用递归从下往上依次构造每个根节点的左右子树的展平形式，并返回该树（子树）的展平形式的首尾节点，用于上一层的展平。
• 同时需注意，当展平了一棵子树时，需要把该子树的根节点的左孩子置空
• 另外，跳出递归的条件看详细代码

代码：

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */// 原地按二叉树先序遍历将二叉树转为单边树class Solution {    public void flatten(TreeNode root) {        flatten2(root);    }    // 以下函数返回两个TreeNode, 第一个为该树(子树)的flatten形式的头结点，第二个为该树(子树)的flatten形式的尾节点    public TreeNode[] flatten2(TreeNode root) {        if (root == null)            return new TreeNode[]{null, null};        TreeNode[] lefts = flatten2(root.left);        TreeNode[] rights = flatten2(root.right);        root.left = null; // 把该节点的左孩子置空        // 头结点不为空，则尾节点肯定也不为空        if (lefts[0] != null) {            root.right = lefts[0];            if (rights[0] != null) {                lefts[1].right = rights[0];                lefts[1].left = null;                return new TreeNode[]{root, rights[1]};               } else {                return new TreeNode[]{root, lefts[1]};            }        } else if (rights[0] != null) {            root.right = rights[0];            return new TreeNode[]{root, rights[1]};        } else {            return new TreeNode[]{root, root};        }    }}

结果：

结论：

遇到使用递归解决问题时，先想想我这个递归函数需要实现的功能是什么，然后再进一步设计递归

转载地址：http://zxesi.baihongyu.com/