7.14(leetcode)

206. 反转链表

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre =null;
        ListNode temp = null;
        ListNode cur = head;
        //循环
        while(cur!=null){
            temp = cur.next;//保存下一个节点
            cur.next = pre;//下一个节点指向头节点
            pre = cur;//讲当前指针的值赋值给头节点
            cur = temp;
        }
        return pre;
    }
}

总的思路cur先行 pre头节点后走cur连接

116. 填充每个节点的下一个右侧节点指针

动画演示+三种实现 116. 填充每个节点的下一个右侧节点指针(王尼玛题解)

dfs题解

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

bfs

class Solution {
    public Node connect(Node root) {
        if(root == null){
            return root;
        }
        Node pre = root;
        //循环条件是当前条件left不为空 当只有根节点
        //所有叶子节点都串联完退出
        while(pre.left!=null){
            Node tmp = pre;
            while(tmp != null){
                //把temp的左右节点都串联
                //外层循环已经判断当前节点的left不为空
                tmp.left.next = tmp.right;
                //下一个不为空说明上一层已经帮我们完成串联
                if(tmp.next!=null){
                    tmp.right.next = tmp.next.left;
                }
                tmp = tmp.next;
            }
            pre = pre.left;
        }
        return root;
    }
}

求最大的二叉树最大深度（迭代法）

class Solution {
    public int maxDepth(TreeNode root) {
    if(root == null) return 0;
    Queue<TreeNode> q =new LinkedList<>();
    q.offer(root);
    int deep = 0;
    while(!q.isEmpty()){
        
        int len = q.size();
        while(len>0){
            TreeNode tempnode = q.poll();
            if(tempnode.left!=null) q.offer(tempnode.left);
            if(tempnode.right!=null) q.offer(tempnode.right);
            len--;
        }
        deep++;
    } 

    return deep;
    
    }
   
}

dfs（递归法）