leetcode-BiNode

[wakisun]

BiNode

链接：https://leetcode-cn.com/problems/binode-lcci/

二叉搜索树

1. 若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
2. 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
3. 任意结点的左、右子树也分别为二叉搜索树。

测试样例

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

分析

根据输入的值来构建整棵二叉搜索树：

由二叉搜索树的特点可以分析出通过中序遍历能够获得一个非递减的序列，即前一个节点的值小于等于后面一个节点的值。而题目中要求转换的单向链表的顺序也就是中序遍历的顺序。要求改造后的链表节点：

node → left = NULL;
node → right = nextNode;

按照中序遍历的顺序，以上图为例，可以看到值为1的节点的right应该指向值为2的节点，而值为3的节点的right应该指向值为4的节点。

题目中给出的节点root指向的是树的根节点，而最后转换的单向链表的节点应该指向的是中序遍历中的第一个节点，也就是图中值为0的节点。

步骤

STEP1：对整棵树进行中序遍历

void dfs(TreeNode *root) {
	if (root != NULL) {
		dfs(root->left);
		dfs(root->right);
	}
}

STEP2: 在中序遍历的基础上改变节点left和right的指向。增加全局的pre来保存中序关系中的前一个节点。同时需要获取第一个节点作为单向链表的头节点指向。

void dfs(TreeNode *root) {
        if (root != NULL) {
            dfs(root->left);
            root->left = NULL;
            if (pre == NULL) {
                ans = root;
            } else {
                pre->right = root;
            }
            pre = root;
            dfs(root->right);
        }
    }

Code

class Solution {
public:
    vector<TreeNode*> v;
    TreeNode *pre, *ans;

    TreeNode* convertBiNode(TreeNode* root) {
        if (root == NULL) {
            return root;
        }

        dfs(root);
        return ans;
    }

    void dfs(TreeNode *root) {
        if (root != NULL) {
            dfs(root->left);
            root->left = NULL;
            if (pre == NULL) {
                ans = root;
            } else {
                pre->right = root;
            }
            pre = root;
            dfs(root->right);
        }
    }
};