leetcode114：二叉树展开为链表

题目链接

leetcode

题目描述

给你二叉树的根结点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历 顺序相同。

C++ 代码

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
using namespace std;

// 二叉树结点的定义
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

const int NULL_NODE = -101;

// 辅助函数：创建二叉树
TreeNode* createTree(const vector<int>& nums) {
    if (nums.empty()) return nullptr;

    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> queue;
    queue.push(root);
    int i = 1;
    while (!queue.empty() && i < nums.size()) {
        TreeNode* node = queue.front(); queue.pop();
        if (nums[i] != NULL_NODE) {
            node->left = new TreeNode(nums[i]);
            queue.push(node->left);
        }
        i ++;
        if (i < nums.size() && nums[i] != NULL_NODE) {
            node->right = new TreeNode(nums[i]);
            queue.push(node->right);
        }
        i ++;
    }

    return root;
}

// 辅助函数：层序遍历打印二叉树
void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;

    queue<TreeNode*> queue;
    queue.push(root);
    while (!queue.empty()) {
        TreeNode* node = queue.front(); queue.pop();
        cout << node->val << " ";
        if (node->left != nullptr) queue.push(node->left);
        if (node->right != nullptr) queue.push(node->right);
    }
    cout << endl;
}

// 辅助函数：释放二叉树
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

/*
    前序遍历一遍，然后把树转成链表。

    时间复杂度：O(n)
        其中 n 是二叉树的结点数。
        前序遍历的时间复杂度是 O(n)，
        前序遍历之后，对每个结点更新左右子结点的信息，时间复杂度也是 O(n)。
    空间复杂度：O(n)
        取决于栈（递归调用栈或迭代中使用的栈），存储前序遍历结果的数组大小，
        栈内的元素个数不会超过 n，数组中的元素个数是 n。
*/
// 递归实现
class Solution_0 {
public:
    void flatten(TreeNode* root) {
        vector<TreeNode*> res;
        preorderTraverse(root, res);
        for (int i = 1; i < res.size(); i ++) {
            TreeNode *prev = res.at(i - 1), *cur = res.at(i);
            prev->left = nullptr;
            prev->right = cur;
        }
    }

    void preorderTraverse(TreeNode* root, vector<TreeNode*>& res) {
        if (root != nullptr) {
            res.push_back(root);
            preorderTraverse(root->left, res);
            preorderTraverse(root->right, res);
        }
    }
};
// 迭代实现
class Solution_1 {
public:
    void flatten(TreeNode* root) {
        vector<TreeNode*> res;
        stack<TreeNode*> stk;
        TreeNode* node = root;
        while (node != nullptr || !stk.empty()) {
            while (node != nullptr) {
                res.push_back(node);
                stk.push(node);
                node = node->left;
            }
            node = stk.top(); stk.pop();
            node = node->right;
        }

        for (int i = 1; i < res.size(); i ++) {
            TreeNode *prev = res.at(i - 1), *cur = res.at(i);
            prev->left = nullptr;
            prev->right = cur;
        }
    }
};

/*
    前序遍历和展开同步进行

    破坏二叉树的结构之后丢失子结点的信息，
    这是因为对左子树进行遍历时，没有存储右子结点的信息，在遍历完左子树之后才获得右子结点的信息。
    对前序遍历进行修改，在遍历左子树之前就获得左右子结点的信息，并存入栈内，
    子结点的信息就不会丢失，就可以将前序遍历和展开为单链表同时进行。

    具体做法：
        不适用于递归实现的前序遍历，只适用于迭代实现的前序遍历。
        每次从栈内弹出一个结点作为当前访问的结点，获得该结点的子结点，
        若子结点不为空，则依次将右子结点和左子结点压入栈内（注意入栈顺序）。

    时间复杂度：O(n)
        其中 n 是二叉树的结点数。
        前序遍历的时间复杂度是 O(n)，
        前序遍历的同时对每个结点更新左右子结点的信息，更新子结点信息的时间复杂度是 O(1)，
        因此总时间复杂度是 O(n)。
    空间复杂度：O(n)
        取决于栈（递归调用栈或迭代中使用的栈），存储前序遍历结果的数组大小，
        栈内的元素个数不会超过 n，数组中的元素个数是 n。
*/
class Solution_2 {
public:
    void flatten(TreeNode* root) {
        if (root == nullptr) return;

        stack<TreeNode*> stk;
        stk.push(root);
        TreeNode *prev = nullptr;
        while (!stk.empty()) {
            TreeNode *cur = stk.top(); stk.pop();
            if (prev != nullptr) {
                prev->left = nullptr;
                prev->right = cur;
            }
            if (cur->right != nullptr) {
                stk.push(cur->right);
            }
            if (cur->left != nullptr) {
                stk.push(cur->left);
            }
            prev = cur;
        }
    }
};

/*
    前序遍历：访问各结点的顺序是根结点、左子树、右子树。
    若一个结点的左子结点为空，则该结点不需要进行展开操作。
    若一个结点的左子结点不为空，则该结点的左子树中的最后一个结点被访问之后，该结点的右子结点被访问。
    该结点的左子树中最后一个被访问的结点是左子树中最右边的结点，也是该结点的前驱结点。
    因此，问题转化成寻找当前结点的前驱结点。

    具体做法：
    对于当前结点，
        若其左子结点不为空，则在其左子树中找到最右边的结点，作为前驱结点，
        将当前结点的右子结点赋给前驱结点的右子结点，
        将当前结点的左子结点赋给当前结点的右子结点，并将当前结点的左子结点设为空。
    当前结点处理结束后，继续处理链表中的下一个结点，直到所有结点都处理结束。

    时间复杂度：O(n)
        其中 n 是二叉树的结点数。
        展开为单链表的过程中，需要对每个结点访问一次。
        在寻找前驱结点的过程中，每个结点最多被额外访问一次。
    空间复杂度：O(1)
*/
class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* cur = root;
        while (cur != nullptr) {
            TreeNode* prev = cur->left;
            if (prev != nullptr) {
                while (prev->right != nullptr) {
                    prev = prev->right;
                }
                prev->right = cur->right;
                cur->right = cur->left;
                cur->left = nullptr;
            }
            cur = cur->right;
        }
    }
};

int main() {
    // 示例输入
    Solution solution;
    vector<int> nums = {1, 2, 5, 3, 4, 6};

    // 创建二叉树
    TreeNode* root = createTree(nums);
    levelOrderTraversal(root);

    // 展开为链表
    solution.flatten(root);

    // 打印结果
    levelOrderTraversal(root);

    // 释放内存
    deleteTree(root);

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

// 定义二叉树节点
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// 创建二叉树
func createTree(values []int) *TreeNode {
	if len(values) == 0 {
		return nil
	}
	root := &TreeNode{Val: values[0]}
	queue := []*TreeNode{root}
	i := 1
	for i < len(values) {
		node := queue[0]
		queue = queue[1:]

		if i < len(values) && values[i] != -1 {
			node.Left = &TreeNode{Val: values[i]}
			queue = append(queue, node.Left)
		}
		i++

		if i < len(values) && values[i] != -1 {
			node.Right = &TreeNode{Val: values[i]}
			queue = append(queue, node.Right)
		}
		i++
	}
	return root
}

// 打印链表（前序遍历）
func printLinkedList(root *TreeNode) string {
	var result []int
	for root != nil {
		result = append(result, root.Val)
		root = root.Right
	}
	return fmt.Sprintf("%v", result)
}

/*
    基本思路：
        将左子树展开为链表。
        将右子树展开为链表。
        将左子树的链表接到右子树链表的前面。

    时间复杂度：O(n)
        其中 n 是二叉树的节点数。
        每个节点被访问一次，递归展开左右子树的时间复杂度为 O(n)。
        在调整链表结构时，找到左子树的最右节点的时间复杂度为 O(n)，因为每个节点最多被访问两次（一次在递归中，一次在寻找最右节点时）。
        因此，总的时间复杂度为 O(n)。
    空间复杂度：O(n)
        递归调用栈的深度为二叉树的高度，最坏情况下（二叉树退化为链表）为 O(n)。
        递归过程中没有使用额外的空间，因此空间复杂度为 O(n)。
*/
// 递归实现：二叉树展开为链表
func flatten(root *TreeNode) {
	if root == nil {
		return
	}

	// 递归展开左右子树
	flatten(root.Left)
	flatten(root.Right)

	// 将左子树移到右子树的位置
	if root.Left != nil {
		// 找到左子树的最右节点
		leftTail := root.Left
		for leftTail.Right != nil {
			leftTail = leftTail.Right
		}

		// 将右子树接到左子树的最右节点
		leftTail.Right = root.Right
		root.Right = root.Left
		root.Left = nil
	}
}

/*
    基本思路：
        使用 Morris 遍历将二叉树展开为链表。
        遍历过程中，利用左子树的最右节点（前驱节点）来调整链表结构。

    时间复杂度：O(n)
        其中 n 是二叉树的节点数。
        每个节点最多被访问两次（一次在寻找前驱节点时，一次在调整链表结构时），
        因此总的时间复杂度为 O(n)。
    空间复杂度：O(1)
        Morris 遍历不使用额外的栈或递归调用栈，空间复杂度为 O(1)。
*/
// 迭代实现：二叉树展开为链表
func flatten_1(root *TreeNode) {
	if root == nil {
		return
	}

	cur := root
	for cur != nil {
		if cur.Left != nil {
			// 找到左子树的最右节点（前驱节点）
			predecessor := cur.Left
			for predecessor.Right != nil && predecessor.Right != cur {
				predecessor = predecessor.Right
			}

			if predecessor.Right == nil {
				// 将当前节点的右子树连接到前驱节点的右子节点上
				predecessor.Right = cur.Right
				// 将当前节点的左子树移到右子树的位置
				cur.Right = cur.Left
				// 将当前节点的左子树置为空
				cur.Left = nil
			} else {
				// 如果前驱节点的右子节点已经连接到当前节点，说明左子树已经展开
				predecessor.Right = nil
			}
		}
		// 移动到下一个节点
		cur = cur.Right
	}
}

func main() {
    // 测试用例
    testCases := []struct {
        values   []int
        expected []int
    }{
        {
            values:   []int{1,2,5,3,4,-1,6},
            expected: []int{1,2,3,4,5,6},
        },
        {
            values:   []int{},
            expected: []int{},
        },
        {
            values:   []int{0},
            expected: []int{0},
        },
    }

    for i, tc := range testCases {
        root := createTree(tc.values)
        fmt.Printf("Test Case %d, Input: values = %v\n", i+1, tc.values)
        flatten(root)
        result := printLinkedList(root)
        expectedStr := fmt.Sprintf("%v", tc.expected)

        if result == expectedStr {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, result)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, result, expectedStr)
        }
    }
}