40 ms C++ code esay to understand


  • 0
    Z
    /**
     * Definition for binary tree with next pointer.
     * struct TreeLinkNode {
     *  int val;
     *  TreeLinkNode *left, *right, *next;
     *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
     * };
     */
    class Solution {
        TreeLinkNode * findFirstSonof(TreeLinkNode *root)
        {
            if(root == NULL) return NULL;
            while(root)
            {
                if(root->left)
                    return root->left;
                if(root->right)
                    return root->right;    
                root=root->next;
            }
            return NULL;
        }
    public:
        void connect(TreeLinkNode *root) {
            if(!root)return;
            TreeLinkNode *firstRootSon  = NULL;// it is the next line's first node
            while(root)
            {
                if(root->left)
                {
                    root->left->next = root->right?root->right:findFirstSonof(root->next);
                    if(!firstRootSon)// 
                    firstRootSon = root->left;
                }
                if(root->right)
                {
                    root->right->next = findFirstSonof(root->next);
                    if(!firstRootSon)
                    firstRootSon = root->right;
                }
                root=root->next;
            }
            if(firstRootSon)
            connect(firstRootSon);
        }
    };

  • 0
    1
    class Solution {
    public:
        TreeLinkNode * findFirstSonof(TreeLinkNode *root)
        {
            if(root == NULL) return NULL;
            while(root)
            {
                if(root->left)
                    return root->left;
                if(root->right)
                    return root->right;    
                root=root->next;
            }
            return NULL;
        }
        void connect(TreeLinkNode *root) {
            if(root==NULL||(root->left==NULL&&root->right==NULL))
               return;
            TreeLinkNode *pnext;
            if(root->left!=NULL)
            {
                root->left->next = root->right?root->right:findFirstSonof(root->next);
            }
            if(root->right!=NULL)
            {
                root->right->next = findFirstSonof(root->next);
            }
            connect(root->right);//注意先右后左,先把右边的链表连起来
            connect(root->left);
        }
    };
    

    受你的启发,我改了下我的代码,这样就不需要firstRootSon 来记录下一行头的位置了


Log in to reply
 

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