114.md

✏️Leetcode基础刷题之(114. Flatten Binary Tree to Linked List)

2019-08-07 吴亲库里 库里的深夜食堂

---

✏️描述

给定一棵二叉树，把二叉树展开平铺成一个单链表(其实还是一棵树，只是节点都是右子树)。

---

✏️题目实例

​

✏️题目分析

利用深度优先搜索找到最左子节点，然后定位到当前节点的父节点，把最左节点赋值给父节点的右子节点，然后再把原来的右子节点变成新的右子节点的右子节点，然后退回到上一层父子节点，重复这个操作。

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {

    /**
     * @param TreeNode $root
     * @return NULL
     */
    function flatten($root) {
        if(!$root) return ;
        if($root->left) $this->flatten($root->left);
        if($root->right) $this->flatten($root->right);
        $node=$root->right;
        $root->right=$root->left;
        $root->left=null;
        while($root->right) $root=$root->right;
        $root->right=$node;
    }
}

---

联系

​