LeetCode 114 Flatten Binary Tree to Linked List

Tag: 二叉树 LeetCode Posted on 2022-02-06 17:45:27 Edited on 2022-02-06 18:03:34 Views: 155

概述

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

以前序顺序将二叉树变成链表。

直接法

首先前序遍历二叉树,构造相应的数组,之后再基于该数组构造对应的链表。

递归法(返回尾节点)

如何处理尾部的 base case?

class Solution {
public:
    void flatten(TreeNode* root) {
        helper(root);
    }
    
    TreeNode* helper(TreeNode* root) {
        if (!root) return nullptr;
        if (!root->left && !root->right) return root; // 这一行可以删去
        auto leftTail = helper(root->left);
        auto rightTail = helper(root->right);
        
        if (leftTail) {
            leftTail->right = root->right;
            root->right = root->left;
        } else {
            root->right = root->right;
        }
        root->left = nullptr;
        
        if (rightTail) return rightTail;
        if (leftTail) return leftTail;
        return root;
    }
};

递归法(不返回尾节点)

实际上我们不需要返回尾节点也可以把右子树对应的链表拼回去,直接 while 遍历过去不就行了。

class Solution {
public:
    void flatten(TreeNode* root) {
        if (!root) return;
        auto originRight = root->right;
        
        flatten(root->left);
        flatten(root->right);
        
        root->right = root->left;
        root->left = nullptr;
        
        auto c = root;
        while (c->right) {
            c = c->right;
        }
        c->right = originRight;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/