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

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


455d9a64e116c44d63020f5b8f40b555.png

题目描述

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

题目分析

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

代码实现

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

上一篇: Leetcode PHP题解--D113 598. Range Addition II

下一篇: Leetcode基础刷题之PHP解析( 115. Distinct Subsequences)