LeetCode 题解

积跬步，至千里。

BiNode

分类：程序员面试金典题解 标签： 树 二叉搜索树 递归 发布于：2020-05-20 ID：17.12

题目描述

来源于 https://leetcode-cn.com/

二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求值的顺序保持不变，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。

返回转换后的单向链表的头节点。

注意：本题相对原题稍作改动

示例：

输入： [4,2,5,1,3,null,6,0]
输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]

提示：

  • 节点数量不会超过 100000。

解法：

中序遍历，始终记录下前一个节点，不断往前一个节点后面加入新的节点，然后把当前节点设为前一个节点。

class Solution {
public:
    TreeNode* convertBiNode(TreeNode* root) {
        TreeNode head(0);
        TreeNode *p = &head;
        traversal(root, p);
        return head.right;
    }

    void traversal(TreeNode* node, TreeNode* &prev){
        if(node == nullptr) return;
        traversal(node->left, prev);
        node->left = nullptr;
        prev->right = node;
        prev = node;
        traversal(node->right, prev);
    }
};

基于栈的中序遍历：

class Solution {
public:
    TreeNode* convertBiNode(TreeNode* root) {
        stack<TreeNode*> stk;
        TreeNode* node = root;
        
        TreeNode head(0);
        TreeNode *p = &head;
        
        while(node || !stk.empty()){
            while(node){
                stk.push(node);
                node = node->left;
            }
            node = stk.top();
            stk.pop();
            p->right = node;
            node->left = nullptr;
            p = node;
            node = node->right;
        }
        return head.right;
    }
};