讨论/《中级算法》 - 填充每个节点的下一个右侧节点指针/
《中级算法》 - 填充每个节点的下一个右侧节点指针
共 10 个回复

解题思路

例如树的层次遍历为[1,2,3,4,5,6,7]

  1. 将树的每个节点的next指针都指向层次遍历的下一个节点:

    [1->2->3->4->5->6->7]

  2. 然后去掉最右节点的next指针:

    [1->null,2->3->NULL,4->5->6->7->NULL]。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
	//特殊情况
    if(root == NULL) return NULL;
	//队列-进行层次遍历
    queue<Node*> q;
	//队列-记录层次遍历
	queue<Node*> tree;
	//使用队列q进行层次遍历,并将层次遍历记录在队列tree中
	q.push(root);
	while(!q.empty()){
		Node* p = q.front();
		q.pop();
		tree.push(p);
		if(p->left != NULL){
			q.push(p->left);	
		}
		if(p->right != NULL){
			q.push(p->right);
		}
	}
	//按层次遍历顺序补上next指针
	while(!tree.empty()){
		Node* p = tree.front();
		tree.pop();
		p->next = tree.front();
	}
	//进行层次遍历(只对最右节点进行),去掉节点的next指针
	q.push(root);
    root->next = NULL;
	while(!q.empty()){
		Node* p = q.front();
		q.pop();
		if(p->right != NULL){
			p->right->next = NULL;
			q.push(p->right);
		}
	}
	//返回跟节点
	return root;
    }
};
//完整测试版
#include<bits/stdc++.h>
#include<math.h>
#include<queue>
using namespace std;
//NODE结构
struct Node{
	int val;
	Node* left;
	Node* right;
	Node* next;
	
	Node():val(0),left(NULL),right(NULL),next(NULL){
	}
	Node(int _val):val(_val),left(NULL),right(NULL),next(NULL){
	}
	Node(int _val,Node* _left,Node* _right,Node* _next):val(_val),left(_left),right(_right),next(_next){
		
	}
};
//构建树
Node* build(int num[],int i){
	if(i<8){
	//默认树的节点只有7个:1,2,3,4,5,6,7
		Node* node = new Node(num[i-1]);
		node->left=build(num,2*i);
		node->right=build(num,2*i+1);
		return node;
	}else{
		return NULL;
	}
	
}
//连接树中next指针
Node* connect(Node* root){
	if(root == NULL) return NULL;
	queue<Node*> q;
	queue<Node*> tree;
	q.push(root);
	while(!q.empty()){
		Node* p = q.front();
		q.pop();
		tree.push(p);
		if(p->left != NULL){
			q.push(p->left);	
		}
		if(p->right != NULL){
			q.push(p->right);
		}
	}
	while(!tree.empty()){
		Node* p = tree.front();
		tree.pop();
		p->next = tree.front();
	}
	q.push(root);
	root->next = NULL;
	while(!q.empty()){
		Node* p = q.front();
		q.pop();
		if(p->right != NULL){
			p->right->next = NULL;
			q.push(p->right);
		}
	}
	return root;
}
//dfs遍历查看树前序遍历
void dfs(Node* root){
	if(root == NULL) return ;
	cout<<root->val;
	dfs(root->left);
	dfs(root->right);
}
int main(){
	int num[7]={1,2,3,4,5,6,7};
	Node* root = build(num,1);//创建树
	dfs(root);//查看是否正确
	connect(root);//连接树中next指针
	return 0;
} 
1

O(n)呀。。队列占用内存的

 class Solution {
        public Node connect(Node root) {
            List<List<Node>> list = new LinkedList<>();
            lfs(root, 0, list);
            for (List<Node> nodeList : list) {
                for (int i = 0; i < nodeList.size() - 1; i++) {
                    Node node = nodeList.get(i);
                    Node next = nodeList.get(i + 1);
                    node.next = next;
                }
            }
            return root;
        }

        void lfs(Node root, int level, List<List<Node>> list) {
            if (root == null) {
                return;
            }
            if (level >= list.size()) {
                list.add(new LinkedList<>());
            }
            list.get(level).add(root);
            lfs(root.left, level + 1, list);
            lfs(root.right, level + 1, list);
        }
    }

层序遍历,然后依次连接

class Solution1 {
        public Node connect(Node root) {
            Map<Integer, Node> list = new HashMap<>();
            lfs(root, 0, list);
            return root;
        }

        void lfs(Node root, int level, Map<Integer, Node> map) {
            if (root == null) {
                return;
            }

            Node node = map.get(level);
            if (node != null) {
                node.next = root;
            }
            map.put(level, root);

            lfs(root.left, level + 1, map);
            lfs(root.right, level + 1, map);
        }
    }

层序遍历,遍历的过程中进行链接

使用队列,空间复杂度算是On还是O1

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        root.next = null;
        connectCore(root.left, root.right);
        return root;
    }

    public void connectCore(Node left, Node right) {
        if (left == null && right == null) {
            return;
        }

        // 左节点连接右节点
        left.next = right;
        // 右节点连接null
        right.next = null;

        // 递归,左右节点的所有子树从左往右依次连接
        // 这样到最后最右子树的next必定指向null,而其它子树也已经依次连接
        connectCore(left.left, left.right);
        connectCore(left.right, right.left);
        connectCore(right.left, right.right);
    }
}
  • 迭代方法
  • 层次遍历思想,基于同层遍历,遍历的同时构建next链接,空间复杂度O(1)
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) 
            return nullptr;
        Node* start = root;
        while (start) {
            Node* last = nullptr;
            Node* nextStart = nullptr;
            Node* p = start; 
            // 构建链接
            while(p) {
                if (p -> left) {
                    build(last, nextStart, p -> left);
                }
                if (p -> right) {
                    build(last, nextStart, p -> right);
                }
                p = p -> next;
            }
            start = nextStart;
        }
        return root;
    }
    void build(Node* &last, Node* &nextStart, Node* p) {
        if (last) {
            // 链接操作
            last -> next = p;
        }
        if (!nextStart) {
            // 记录当前层的开始
            nextStart = p;
        }
        // 移动同层指针
        last = p;
    }
};

非递归求解

class Solution {
    public Node connect(Node root) {
        if(root == null)
            return root;
        
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            for(int i = 0;i < size;i++) {
                Node node = queue.poll();
                if(i != size - 1)
                    node.next = queue.peek();   // 将当前节点指向队列首节点

                if(node.left != null)
                    queue.offer(node.left);
                if(node.right != null)
                    queue.offer(node.right);
            }
        }
        return root;
    }
}

递归求解

class Solution {
    public Node connect(Node root) {
        if(root == null)
            return root;
        
        Node left = connect(root.left);
        Node right = connect(root.right);
        
        while(left != null) {
            left.next = right;
            left = left.right;
            right = right.left;
        }

        return root;
    }
}

so cute

试试讨论区