力扣hot100—二叉树15题

前、中、后序遍历的递归与非递归写法

递归写法很容易，非递归写法需要用到模拟栈。
递归写法，对于前中后序遍历，只需要更改递归函数mid的执行顺序即可：

class Solution {
    List<Integer> res = new ArrayList<>();
    void mid(TreeNode node){
        if(node == null) return;
        mid(node.left);
        res.add(node.val);
        mid(node.right);
        return;
    }
    public List<Integer> inorderTraversal(TreeNode root) {
        mid(root);
        return res;
    }
}

中序遍历的迭代写法，用栈模拟递归栈出来，双重循环，外层循环遍历栈的情况，内层循环不断把当前访问节点的左节点压入栈。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> s = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !s.isEmpty()) {
            // 深入左子树，压栈途径节点
            while (cur != null) {
                s.push(cur);
                cur = cur.left;
            }
            
            cur = s.pop();
            res.add(cur.val);
            cur = cur.right;
        }
        return res;
    }
}

前序遍历的写法，同样和中序遍历一致，用栈来模拟。

class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null) return new ArrayList<Integer>();
        Stack<TreeNode> s = new Stack<>();
        s.push(root);
        TreeNode cur = root;
        while(cur != null || !s.isEmpty()){
            cur = s.pop();
            if(cur != null) res.add(cur.val);
            if(cur != null) s.push(cur.right);
            if(cur != null) s.push(cur.left);
        }
        return res;
    }
}

后序遍历，简单的方式就是基于前序遍历，最后reverse一下List。

class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null) return new ArrayList<Integer>();
        Stack<TreeNode> s = new Stack<>();
        s.push(root);
        TreeNode cur = root;
        // 维护访问顺序为 根右左，之后reverse一下
        while(cur != null || !s.isEmpty()){
            cur = s.pop();
            if(cur != null) res.add(cur.val);
            if(cur != null) s.push(cur.left);
            if(cur != null) s.push(cur.right);
        }
        Collections.reverse(res);
        return res;
    }
}

二叉树的最大深度

简单DFS

class Solution {
    public int dfs(TreeNode node){
        if(node == null) return 0;
        int lh = dfs(node.left) + 1;
        int rh = dfs(node.right) + 1;
        return Math.max(lh, rh);
    }
    public int maxDepth(TreeNode root) {
        return dfs(root);
    }
}

翻转二叉树

递归法：

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

还有一种方法是层序遍历方式，用队列实现BFS。

class Solution {
	public TreeNode invertTree(TreeNode root) {
		if(root==null) {
			return null;
		}
		//将二叉树中的节点逐层放入队列中，再迭代处理队列中的元素
		LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
		queue.add(root);
		while(!queue.isEmpty()) {
			//每次都从队列中拿一个节点，并交换这个节点的左右子树
			TreeNode tmp = queue.poll();
			TreeNode left = tmp.left;
			tmp.left = tmp.right;
			tmp.right = left;
			//如果当前节点的左子树不为空，则放入队列等待后续处理
			if(tmp.left!=null) {
				queue.add(tmp.left);
			}
			//如果当前节点的右子树不为空，则放入队列等待后续处理
			if(tmp.right!=null) {
				queue.add(tmp.right);
			}
			
		}
		//返回处理完的根节点
		return root;
	}
}

对称二叉树

递归，思路：比较左右节点，递归比较左节点左孩子与右节点右孩子 && 左节点右孩子与右节点左孩子

class Solution {
    
    public boolean isSymmetric(TreeNode root) {
        return check(root.left, root.right);
    }
    public boolean check(TreeNode l, TreeNode r){
        if(l == null && r == null) return true;
        if(l == null || r == null) return false;
        
        return l.val == r.val && check(l.left, r.right) && check(l.right, r.left);
    }
}

二叉树的直径

和求深度差不多

class Solution {
    int res = 0;
    public int dfs(TreeNode node){
        if(node == null) return 0;
        int l = dfs(node.left);
        int r = dfs(node.right);
        
        // 维护最大深度和
        res = Math.max(res, l + r + 1);

        // 返回当前点深度
        return Math.max(l, r) + 1;
    }
    public int diameterOfBinaryTree(TreeNode root) {
        // 当前点的直径 = 左子树最大直径 + 右子树最大直径
        dfs(root);
        // 记录的是深度 直径要-1
        return res - 1;
    }
}

二叉树的层序遍历

队列BFS

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        Queue<TreeNode> q = new LinkedList<>();
        if(root != null) q.offer(root);
        while(!q.isEmpty()){
            int levelSize =q.size();
            List<Integer> list = new LinkedList<>();
            for(int i = 0; i < levelSize; i++){
                TreeNode cur = q.peek();
                q.remove();
                list.add(cur.val);
                if(cur.left !=  null) q.offer(cur.left);
                if(cur.right != null) q.offer(cur.right);
            }
            res.add(list);
        }
        return res;
    }
}

将有序数组转换为二叉搜索树

用递归的方法，二分开数组的左右两侧，每次递归都找出区间的中点作为root，然后继续递归左右两侧的值。

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums, 0, nums.length - 1);
    }
    public TreeNode dfs(int[] nums, int low, int hight){
        if(low > hight){
            return null;
        }
        int mid = (low + hight) / 2;
        // 选择 中间偏左的作为根节点
        TreeNode root = new TreeNode(nums[mid]);
        // 左子树是小于root值的 即数组的左部分
        root.left = dfs(nums, low, mid - 1);
        // 同理 右子树是大于root值的
        root.right = dfs(nums, mid + 1, hight);
        return root;
    }
}

验证二叉搜索树

由搜索树的性质，左<中<右，与中序遍历的序列一致，要判断二叉搜索树只需要验证中序遍历是否满足增序即可。

class Solution {
    public boolean isValidBST(TreeNode root) {
        Stack<TreeNode> st = new Stack<>();
        TreeNode cur = root;
        long preVal = Long.MIN_VALUE;
        
        while(cur != null || !st.isEmpty()){
            while(cur != null){
                st.push(cur);
                cur = cur.left;
            }
            
            cur = st.pop();

            if(cur != null){
                // 如果小于等于前一个 说明不是二叉搜索树
                if(cur.val <= preVal) return false;
                preVal = cur.val;
                cur = cur.right;
            }
        }
        return true;
    }
}

二叉搜索树中第 K 小的元素

最直观的方式就是中序遍历找出第k个。用栈迭代法的话，可以找到就停止迭代，速度更优。

class Solution {

    List<Integer> nums = new ArrayList<>();
    int cnt = 0;
    int res = 0;
    public void dfs(TreeNode root, int k){
        if(root == null) return;
        dfs(root.left, k);
        cnt++;
        if(cnt == k){
            res = root.val;
        }
        dfs(root.right, k);
        return;
    }
    public int kthSmallest(TreeNode root, int k) {
        dfs(root, k);
        return res;
    }
}

二叉树的右视图

思路：先递归右子树，再递归左子树，当某个深度首次到达时，对应的节点就在右视图中。

class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        dfs(root, 0);
        return res;
    }
    public void dfs(TreeNode root, int depth){
        if(root == null) return;
        // 如果这个深度首次到达 就把这个点加进去
        if(res.size() == depth){
            res.add(root.val);
        }
        dfs(root.right, depth + 1);
        dfs(root.left, depth + 1);
    }
}

二叉树展开为链表

直观的做法可以先先序遍历一遍，把节点存List里面，然后第二次迭代再维护。但是这种情况，会有额外的空间需求，如果要O1空间复杂度的话，要用循环迭代，规则不好找，但是满好理解：

遍历找到当前根R左子树的最右节点A
将节点A的右子树设置为根节点R的右子树
节点A变成根节点R的右子树

画图：

    R
   / \
  2   5
 / \   \
3   A   6

//将节点A的右子树设置为根节点R的右子树
    A
     \
      5        
       \        
        6              
//将原来的右子树接到左子树的最右边节点
    R
     \
      2          
     / \          
    3   A 
         \
          5
           \
            6
            
 //将 2 的左子树插入到右子树的地方
    R
     \
      2          
       \          
        3       A  
                 \
                  5
                   \
                    6   
        
 //将原来的右子树接到左子树的最右边节点
    R
     \
      2          
       \          
        3      
         \
          A  
           \
            5
             \
              6

代码：

class Solution {
    public void flatten(TreeNode root) {
        TreeNode head = root;
        while(root != null){
            if(root.left != null){
                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;
        }
    }
}

中序遍历和前序遍历还原二叉树

挺难的，不好理解。前序遍历是根-左-右，中序遍历是左-根-右。
递归函数需要维护两个序列的窗口。设置前序遍历的窗口为l1、r1、中序遍历的为l2、r2。
对于每一次递归：

前序遍历的l1就是这次递归的根节点，基于前序遍历，找出根节点在中序遍历的位置in_root。
那么就可以得到，当前迭代的根节点，左侧的节点数目为：in_root – l2 = size_left_subtree;
那么就可以开始维护递归节点了。当前节点的左子树root.left将等于：
handler(preorder, inorder, l1+1, l1 + size_left_subtree, l2, in_root-1);
即先序遍历的4个窗口为：l1+1（意思是l1的下一个节点，因为l1节点就是当前迭代维护完毕的根节点）、l1+size_left_subtree（意思是当前左子树需要维护的所有节点数）、l2（中序遍历的左侧窗口起点）、in_root-1（中序遍历的右侧窗口，因为维护的是左子树，根节点是in_root，所以左子树的右侧窗口是in_root-1）
同理可以得出右子树的维护方式。

class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    int n;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        n = preorder.length;
        return handler(preorder, inorder, 0, n-1, 0, n-1);
    }
    // 参数为两个遍历序列和他们各自的序列边界
    public TreeNode handler(int[] preorder, int[] inorder, int l1, int r1, int l2, int r2){
        if(l1 > r1){
            return null;
        }
        // 前序遍历的第一个节点就是根节点 
        int pre_root = l1;
        // 找出根节点在中序遍历中的位置
        int in_root = findInLocation(l1, preorder, inorder);

        TreeNode root = new TreeNode(preorder[pre_root]);
        // 左子树的节点数目 = 中序遍历的根节点位置-中序遍历左侧边界
        int size_left_subtree = in_root - l2;
        // 递归构造
        // 递归参数的含义为：
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root.left = handler(preorder, inorder, l1+1, l1 + size_left_subtree, l2, in_root-1);
        root.right = handler(preorder, inorder, l1 + 1 + size_left_subtree, r1, in_root + 1, r2);
        return root;
    }

    public int findInLocation(int pre_left, int[] preorder, int[] inorder){
        for(int i = 0; i < n; i++){
            if(preorder[pre_left] == inorder[i]) return i;
        }
        return -1;
    }
    
}

路径总和Ⅲ

这题用DFS的话，关键点在于路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。递归不能直接返回结果。

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if(root == null) return 0;
        int ret = 0;
        ret = dfs(root, targetSum);
        ret += pathSum(root.left, targetSum);
        ret += pathSum(root.right, targetSum);
        return ret;
        
    }
    public int dfs(TreeNode root, long targetSum){
        if(root == null) return 0;
        int ret = 0;
        if(root.val == targetSum){
            ret++;
        }
        ret += dfs(root.left, targetSum - root.val);
        ret += dfs(root.right, targetSum - root.val);
        return ret;
    }
}

二叉树的最近公共祖先

定义root如果是p、q的最近公共祖先，则有三种情况：

p、q在root的子树中，且p、q分别属于root的不同侧子树，
p是root，q在p的子树中
q是root，p在q的子树中

递归的逻辑就是，判断p和q是否分列左右子树，如果是说明当前点就是祖先，如果不说说明他们其中有一个是另一个的祖先。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果root是p或者q 直接返回就是结果 如果是空也返回
        if(root == null || root == p || root == q) return root;

        // 递归找左右子树 看看左右子树里面有没有p和q
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // 如果left和righ都不为null 说明root就是最近公共祖先
        if(left!= null && right != null) return root;

        // 如果有一个为null 说明p和q在不同侧子树 且非null的那个就是祖先(非null的那个先遇到 导致之后的那个永远遇不到)
        if(left != null) return left;
        return right;

    }
}

二叉树中的最大路径和，

递归，显然，对于当前节点有四个选择：

我自己就是一条路径
只跟左子节点合并成一条路径
只跟右子节点合并成一条路径
以自己为桥梁，跟左、右子节点合并成一条路径

为了方便维护最大路径，直接定义一个非局部的pathSum

class Solution {

    int pathSum = Integer.MIN_VALUE;

    public int dfs(TreeNode node){
        if(node == null) return 0;
        int left = dfs(node.left);
        int right = dfs(node.right);
        // 当前节点的情况 有4种选择 判断出最大的那种
        // 三种情况比最大的：仅本节点，本节点+左子节点，本节点+右子节点
        int res = Math.max(node.val, node.val + Math.max(left, right));
        // 一种特殊情况 即以本节点为桥 连接左右子节点（不考虑本节点的父节点）
        int bridge = node.val + left + right;
        // 维护出最大的 要么是pathSum本身 要么是特殊情况 要么是前三种情况中最大的
        pathSum = Math.max(pathSum, Math.max(res, bridge));
        return res;
    }

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return pathSum;
    }

}