Leetcode基础刷题之PHP解析(114. Flatten Binary Tree to Linked List）

Created 5 years ago by 吴亲库里, Updated 5 years ago Revision #1 2497 views 0 likes 0 collects

上一题链接Leetcode基础刷题之PHP解析(113. Path Sum II)

题目描述

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

题目分析

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

代码实现

/**
 * 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;
    }
}

Github整理地址:https://github.com/wuqinqiang/leetcode-php