Leetcode二叉树部分笔记

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

1.二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

**解题思路：**如果用广度优先遍历的话，设置一个队列，quque.offer代表让节点进入队列，判断当前队列内还有没有值，如果有则把它的左右孩子放进来，并把size–，每清空一次队列，代表遍历了一层，建一个计数器每遍历一层，计数器加一。最终得到深度。

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

**解题思路2：**使用深度优先遍历，采用递归：假设深度优先到最后一层，执行这个函数，左孩子为null，右孩子为null，左孩子执行这个函数，返回0，右孩子执行这个函数，也返回0。该节点返回1，它的上一层 leftHeight就成1了。同理，如果他的上一层没有右孩子，则右孩子返回0，则这个上一层返回2。以此类推。

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = maxDepth(root.left);
            int rightHeight = maxDepth(root.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}

2.同样的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

**解题思路：**使用深度优先遍历。假设p和q都到了最后一层，p,left == null，q.left ==null,因此函数返回true，同理p.right == null 并且q.right == null，同样返回true，这样该节点返回一个true，返回给上一层，看看第一层是不是都是true。

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null && q==null){
            return true;
        }else if(p==null || q==null){
            return false;
        }else if(p.val != q.val){
            return false;
        }else{
            return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
        }

        

    }
}

3.翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

解题思路：假设在最后一层的两个节点，这两个节点的四个孩子都是null，返回他们本身就可以，这两个节点的上一层的父节点，接收到下面返回上来的left和right，并对这两个进行置换，把它自身返回上去，以此类推。

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

4.对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

**解题思路：**也就是判断L.left和R.right 以及 L.right = R.left，是否都能同时到达最底部，如果没有则说明不对称。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return root == null || recur(root.left, root.right);
    }
    boolean recur(TreeNode L, TreeNode R) {
        if (L == null && R == null) return true;
        if (L == null || R == null || L.val != R.val) return false;
        return recur(L.left, R.right) && recur(L.right, R.left);
    }
}

作者：Krahets
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

**5. 填充每个节点的下一个右侧节点指针 II

给定一个二叉树：

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

**解题思路：**层序遍历，设置一个指针，如果当前层的大小不为1，则说明后面还有，让这个指针的next指向poll出来的节点，再让指针更新，如果大小为1，则不做任何操作。

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        Queue<Node> queue = new LinkedList<Node>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            Node last = null;
            for (int i = 1; i <= n; ++i) {
                Node f = queue.poll();
                if (f.left != null) {
                    queue.offer(f.left);
                }
                if (f.right != null) {
                    queue.offer(f.right);
                }
                if (i != 1) {
                    last.next = f;
                }
                last = f;
            }
        }
        return root;
    }
}

6. 二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

**解题思路:**设置一个pre，专门寻找root节点的left孩子的最右侧孩子，到达最右侧后让最右侧的右指针指向root的右孩子，让root的右指针指向root的左孩子，再让root向下走，遍历一遍。

class Solution {
    public void flatten(TreeNode root) {
    while (root != null) { 
        //左子树为 null，直接考虑下一个节点
        if (root.left == null) {
            root = root.right;
        } else {
            // 找左子树最右边的节点
            TreeNode pre = root.left;
            while (pre.right != null) {
                pre = pre.right;
            } 
            //将原来的右子树接到左子树的最右边节点
            pre.right = root.right;
            // 将左子树插入到右子树的地方
            root.right = root.left;
            root.left = null;
            // 考虑下一个节点
            root = root.right;
        }
    }
}

7. 路经总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

**解题思路：**假设在最后一层，发现root.left == null && root.right ==null 则返回当前value和sum值是否相等的判断，如果相等，则说明成立，直接返回true，如果不相等则返回false。

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return sum == root.val;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

8.完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。

class Solution {
    public int countNodes(TreeNode root) {
    	if(root == null) {
    		return 0;
    	}
    	int left = countNodes(root.left);
    	int right = countNodes(root.right);
    	
    	return left+right+1;
    	
    }
}