[Fixed & Closed] An erroneous C++ program


  • 0

    Corrected Code: (Thanks!)

    class Solution {
    public:
    	void flatten(TreeNode* root) {
    		flattenCore(root);
    		return;
    	}
    	TreeNode*& flattenCore(TreeNode*& root) {
    		if (root == nullptr) {
    			return root;
    		}
    		else {
    			TreeNode* lchild = root->left;
    			TreeNode* rchild = root->right;
    			root->left = nullptr;
    			root->right = lchild;
    			TreeNode*& llast = flattenCore(root->right) = rchild;
    			llast = rchild;
    			return flattenCore(llast);
    		}
    	}
    };
    

    ================ ORIGINAL POST ==============

    My code does not work for the following test case:

    Input: [1,2]

    My wrong output: [1]

    Expected output: [1,null,2]

    But I do not know why. I tried to use Visual Studio to debug, and found some very strange behavior.

    My idea is as follows: Recursively call a function called flattenCore, which returns the end of the linked list (as a reference to the last pointer), to simulate a preorder travesal. And then link the remaining nodes to the reference just returned.

    Thanks a lot!

    class Solution {
    public:
    	void flatten(TreeNode* root) {
    		flattenCore(root);
    		return;
    	}
    	TreeNode*& flattenCore(TreeNode*& root) {
    		TreeNode*& ret = root;
    
    		// if root is a null pointer, return it as is
    		if (root != nullptr) {
    			// store the value of root->left and root->right
    			TreeNode* lchild = root->left;
    			TreeNode* rchild = root->right;
    
    			// redirect root->right to lchild
    			root->left = nullptr;
    			root->right = lchild;
    
    			// recusively call flattenCore, get the last pointer
    			TreeNode*& llast = flattenCore(root->right); // this seems okay.
    
    			// link the last pointer to rchild
    			llast = rchild;
    
    			// recursively call flattenCore, but there seems problematic
    			ret = flattenCore(llast); // when calling this function in a subroutine, the value of root changes. That is weird!
    		}
    		return ret;
    	}
    };
    

    In the sequal is an executable program set with debug codes:

    You can add a data debug point on PrintTree::root to see the changes of values.

    When executing this file, it will report an error to tell us I want to access root->right, where root is a nullptr. So that is a runtime error.

    #include <iostream>
    
    using namespace std;
    
    /**
    * Definition for a binary tree node. */
    struct TreeNode {
    	int val;
    	TreeNode *left;
    	TreeNode *right;
    	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    
    class PrintTree { // This class is for debug only.
    public:
    	static TreeNode* root;
    
    	static void setRoot(TreeNode* _root) {
    		root = _root;
    		return;
    	}
    
    	static void printTree() {
    		printTreeCore(root);
    	}
    
    	static void printTreeCore(TreeNode* _root) {
    		if (_root == nullptr) {
    			cout << "Null Node" << endl;
    		}
    		else {
    			cout << "Node: " << reinterpret_cast<unsigned int>(_root) << endl;
    			cout << "Left: ";
    			printTreeCore(_root->left);
    			cout << "Right: ";
    			printTreeCore(_root->right);
    		}
    	}
    };
    TreeNode* PrintTree::root = nullptr;
            
    class Solution {
    public:
    	void flatten(TreeNode* root) {
    		flattenCore(root);
    		return;
    	}
    	TreeNode*& flattenCore(TreeNode*& root) {
    		// cout << "param: " << reinterpret_cast<unsigned int>(root) << endl;
    		TreeNode*& ret = root;
    		if (root != nullptr) {
    			TreeNode* lchild = root->left;
    			TreeNode* rchild = root->right;
    			root->left = nullptr;
    			root->right = lchild;
    			// cout << "if:flatten0:param: " << reinterpret_cast<unsigned int>(root) << endl;
    			// cout << "if:flatten0:root->right: " << reinterpret_cast<unsigned int>(root->right) << endl;
    			TreeNode*& llast = flattenCore(root->right);
    			// cout << "if:flatten1:param: " << reinterpret_cast<unsigned int>(root) << endl;
    			// cout << "if:flatten1:root->right: " << reinterpret_cast<unsigned int>(root->right) << endl;
    			// cout << "if:flatten1:llast: " << reinterpret_cast<unsigned int>(llast) << endl;
    			llast = rchild;
    			// cout << "if:flatten1:llast: " << reinterpret_cast<unsigned int>(llast) << endl;
    			// cout << "if:flatten1:root: " << reinterpret_cast<unsigned int>(root) << endl;
    			// PrintTree::printTree();
    			ret = flattenCore(llast);
    			// PrintTree::printTree();
    			// cout << "if:flatten2:root: " << reinterpret_cast<unsigned int>(root) << endl;
    			// cout << "if:flatten2:root->right: " << reinterpret_cast<unsigned int>(root->right) << endl;
    		}
    		//cout << "ret: " << reinterpret_cast<unsigned int>(ret) << endl;
    		return ret;
    	}
    };
    
    int main() {
    	Solution solution;
    	TreeNode rootNode(1);
    	TreeNode leftNode(2);
    	rootNode.left = &leftNode;
    	cout << reinterpret_cast<unsigned int>(&rootNode) << endl;
    	cout << reinterpret_cast<unsigned int>(&leftNode) << endl;
    	PrintTree::setRoot(&rootNode);
    	solution.flatten(&rootNode);
    	cout << reinterpret_cast<unsigned int>(rootNode.left) << endl;
    	cout << reinterpret_cast<unsigned int>(rootNode.right) << endl;
    	return 0;;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.