剑指offer

深搜递归

简单的自底向上深搜 71. 二叉树的深度

如果到了叶节点，depth = 1，否则取左子节点和右子节点的max + 1

  1. class Solution {
  2.     public int treeDepth(TreeNode root) {
  3.         //如果到了叶节点，depth = 1，否则取左子节点和右子节点的max + 1
  4.         if (root == null) return 0;
  5.         return Math.max(treeDepth(root.left), treeDepth(root.right)) + 1;
  6.     }
  7. }

(简单递归)合并二叉树

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
  18.         /**
  19.             保证r1一定存在
  20.             前序遍历把两个节点相加
  21.          */
  22.         if (root1 == null) {
  23.             TreeNode t = root1; root1 = root2; root2 = t;
  24.         }
  25.         if (root1 == null) return null;
  26.         if (root2 != null)
  27.             root1.val += root2.val;
  28.         // 当r1的左右子树可能为空的时候，接上r2的左右子树
  29.         root1.left = mergeTrees(root1.left, root2!=null?root2.left:null); 
  30.         root1.right = mergeTrees(root1.right,root2!=null?root2.right:null);
  31.         return  root1;
  32.     }
  33. }

加入判断条件的自底向上深搜 72. 平衡二叉树

  1. class Solution {
  2.     boolean flag = true;
  3.     public boolean isBalanced(TreeNode root) {
  4.         //在算出树的高度的情况下，判断左右子树的高度差 是否 > 1
  5.         dfs(root);
  6.         return flag;
  7.     }
  9.     int dfs(TreeNode root){
  10.         if (root == null) return 0;
  11.         if (!flag) return -1;
  12.         int lDepth = dfs(root.left), rDepth = dfs(root.right);
  13.         if (flag && Math.abs(lDepth - rDepth) > 1) flag = false;
  14.         return Math.max(lDepth, rDepth) + 1;
  15.     }
  16. }

自顶向下深搜判断235. 二叉搜索树的最近公共祖先

思路

如果pq分别是root的两边，那么root肯定是最近祖先

如果pq在一边，说明需要向这一边递归，找最新祖先

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  11. class Solution {
  12.     TreeNode p, q;
  13.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  14.         //如果pq分别是root的两边，那么root肯定是最近祖先
  15.         //如果pq在一边，说明需要向这一边递归，找最新祖先
  16.         //如果pq == root，root就是最近祖先
  17.         if (root == null) return null;
  18.         if (p.val > q.val){
  19.             TreeNode tmp = q;
  20.             q = p;
  21.             p = tmp;
  22.         }
  23.         this.p = p; this.q = q;
  24.         return hasChd(root);
  25.     }
  27.     public TreeNode hasChd(TreeNode root){
  28.         if (p.val <= root.val && q.val >= root.val) return root;
  29.         if (root == p || root == q) return root;
  30.         else if (q.val <= root.val){
  31.             root = hasChd(root.left);
  32.         }
  33.         else 
  34.             root = hasChd(root.right);
  35.         return root;
  36.     }
  37. }

自底向上递归236. 二叉树的最近公共祖先

我们能看出来自顶向下和自底向上两种遍历方式的不同

自顶向下

  1. if (xx)return cur(...);

自底向上

  1. int state = dfs(root.left, p, q);

思路

自底向上，如果找到了pq点，就返回root，此时root是最近公共祖先

注意state是在递归中创建的。表示这一层中root的子树中有没有找到同时pq节点。

如果不是在递归中创建的，就是整个子树中有没有找到pq两个节点。

递归的状态：dfs(root, p,q) 以root为根的子树中有没有找到对应pq。

顺序： 自底向上，向根传递当前层的状态。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     TreeNode ans;
  12.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  13.         //自底向上，如果找到了pq点，就返回root，此时root是最近公共祖先
  14.         dfs(root, p, q);
  15.         return ans;
  16.     }
  18.     public int dfs(TreeNode root, TreeNode p, TreeNode q){
  19.         //state是以root为根节点的树中能不能找到pq节点
  20.         if (root == null) return 0;
  21.         int state = dfs(root.left, p, q);
  22.         if (root == p) state |= 1;
  23.         if (root == q) state |= 2;
  24.         state |= dfs(root.right, p, q); 
  25.         if (state == 3 && ans == null) ans = root;
  26.         return state;
  27.     }
  28. }

与上题一样88. 树中两个结点的最低公共祖先

深搜递归 + 条件判断47. 二叉树中和为某一值的路径

中序遍历从根节点遍历到叶节点，同时更新sum1、记录list，如果sum1 == sum，更新list，否则清空

  1. class Solution {
  2.     List<List<Integer>> res ;
  3.     Deque<Integer>  path;
  4.     int sum1 = 0;
  5.     int sum;
  6.     public List<List<Integer>> findPath(TreeNode root, int sum) {
  7.         //中序遍历从根节点遍历到叶节点，同时更新sum1、记录list，如果sum1 == sum，更新list，否则清空
  8.         this.sum = sum;
  9.         res = new ArrayList<List<Integer>>();
  10.         path = new LinkedList<Integer>();
  11.         dfs(root);
  12.         return res;
  13.     }
  15.     public void dfs(TreeNode root){
  16.         if (root == null) return ;
  17.         sum1 += root.val;
  18.         path.addLast(root.val);
  19.         if (sum1 == sum && root.left == null && root.right == null) res.add(new ArrayList<Integer>(path));
  20.         dfs(root.left);
  21.         dfs(root.right);
  22.         path.pollLast();
  23.         sum1 -= root.val;
  24.     }
  25. }

递归DP（树形DP）124. 二叉树中的最大路径和)

dp思路：

  1. f[i]表示以i为最高点(路径中两个端点的最近公共祖先)向一个方向前进(左、右或者停止)的最大路径和
  2. f[i]有三种选择，在i处停止；向左（如果向左的路径和 > 0）；向右(如果向右的路径和 > 0)，并且沿着最高点的左右子节点的两条不同路径是相互独立的，因此只要求三种情况的最大值
  3. f[i] = Max(max(0,vi + f[left]), max(0,vi + f[right])) + vi
  4. 最后答案： f[left] + f[right] + vi的全局最大值 (从i左边向下走和右边向下走连成的一条路径)
  1. class Solution {
  2.     int ans = Integer.MIN_VALUE;
  3.     public int maxPathSum(TreeNode root) {
  4.         /*
  5.         dp思路： f[i]表示以i为最高点(路径中两个端点的最近公共祖先)向一个方向前进(左、右或者停止)的最大路径和 
  6.         f[i]有三种选择，在i处停止；向左（如果向左的路径和 > 0）；向右(如果向右的路径和 > 0)，并且沿着最高点的左右子节点的两条不同路径是相互独立的，因此只要求三种情况的最大值
  7.         f[i] = Max(max(0,vi + f[left]), max(0,vi + f[right]))  + vi
  9.         最后答案： f[left] + f[right] + vi的全局最大值 (从i左边向下走和右边向下走连成的一条路径)
  10.         */
  11.         //递归来实现dp，只需要记录全局最大值即可
  12.         recur(root);
  13.         return ans;
  14.     }
  15.     //每一层代表当前节点向一个方向前进
  16.     public int recur(TreeNode root){
  17.         if (root == null) return 0;
  18.         int left = Math.max(0, recur(root.left));//0代表不向左
  19.         int right = Math.max(0, recur(root.right));
  20.         ans = Math.max(ans, left + right + root.val);
  21.         //返回前节点向一个方向前进的最大值
  22.         return root.val + Math.max(left, right);
  23.     }
  24. }

递归深搜遍历37. 树的子结构 - AcWing题库

思路

  • 遍历子树A， 判断子树B是否是A的子结构 isSub(A, B)

    • 如果是，直接返回true
    • 如果不是，分别判断子树B是否是A.left / A.right的子结构
    • 注意当A为空的时候，代表遍历完了子树还没有匹配，返回false；B为空，代表空树，根据题目，返回false

isSub函数

  • 判断A和B当前值

    • 如果相等，递归分别判断 左右子树是否相等
    • 如果不相等，返回false
    • 注意，如果B遍历结束，就代表b所有的值都是A的子结构，返回true
    • 如果A遍历结束，而B没有结束，代表B不是A子结构，返回false
  1. class Solution {
  2.     public boolean isSubStructure(TreeNode A, TreeNode B) {
  3.         if (A == null || B == null) return false;
  4.         if (isSub(A, B)) return true;
  5.         else return isSubStructure(A.left, B) || isSubStructure(A.right, B);
  6.     }
  8.     public boolean isSub(TreeNode a, TreeNode b){
  9.         if (b == null) return true;
  10.         if (a == null) return false;
  11.         if (a.val == b.val) return isSub(a.left, b.left) && isSub(a.right, b.right);
  12.         else return false;
  13.     }
  14. }

反转二叉树38. 二叉树的镜像 - AcWing题库

思路

除了root之外，无论是不是空节点，都将其和对应的兄弟节点交换

  1. //自顶向下
  2. class Solution {
  3.     public void mirror(TreeNode root) {
  4.         if (root == null) return ;
  5.         TreeNode tmp = root.right;
  6.         root.right = root.left;
  7.         root.left = tmp;
  8.         mirror(root.left); mirror(root.right);
  9.     }
  10. }
  12. //自底向上
  13. class Solution {
  14.     public TreeNode mirrorTree(TreeNode root) {
  15.         if (root == null) return null;
  16.         mirrorTree(root.left); 
  17.         mirrorTree(root.right);
  18.         TreeNode tmp = root.right;
  19.         root.right = root.left;
  20.         root.left = tmp;
  21.         return root;
  22.     }
  23. }

递归深搜对称节点 对称的二叉树 - 力扣

思路

向下递归判断当前树的左子节点和右子节点。

  • 如果其中一个节点是空，两个都为空才对称
  • 如果两个节点的值相同，继续递归判断 左子节点的右子节点 和 右子节点的左子节点 ； 右子节点的右子节点 和 左子节点的左子节点 是否相同
  1. class Solution {
  2.     public boolean isSymmetric(TreeNode root) {
  3.         if (root == null) return true;
  4.         return dfs(root.left, root.right);
  5.     }
  6.     public boolean dfs(TreeNode p, TreeNode q){
  7.         if (p == null || q == null) return p == null && q == null;
  8.         if (p.val == q.val){
  9.             return dfs(p.right, q.left) && dfs(p.left, q.right);
  10.         }
  11.         else return false;
  12.     }
  13. }

迭代方式:一般迭代方式都新建一个queue，把递归方式中下一层的元素放入queue中。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        if (root == null) return true;
        queue.add(root.left); queue.add(root.right);
        while (!queue.isEmpty()){
            TreeNode p = queue.poll(), q = queue.remove();
            if (p == null && q == null) continue;
            if (p == null || q == null || p.val != q.val) return false;
            queue.add(q.left); queue.add(p.right);
            queue.add(q.right); queue.add(p.left);
        }
        return true;
    }
}

普通中序遍历 70. 二叉搜索树的第k个结点 - AcWing题库

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int k;TreeNode tmp = null;
    public TreeNode kthNode(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return tmp;
    }
     //优化思路：维护一个值val，代表以当前root为根的子树中有多少个元素
     //val + 1 == k 表示当前点的父节点是目标
     // val + 1 < k 表示k在父节点的右子树种
     // val + 1 > k 在左子树中
    void dfs(TreeNode root){
        //中序遍历，每次遍历到一个节点，k--，当k=0的时候，对应节点答案. 注意剪枝，当k = 0，后面就不需要再递归了
        if (root == null) return ;
        dfs(root.left);
        if (tmp == null && --k <= 0) {tmp = root; return ;};
        dfs(root.right);
        return;
    }
}

递归108. 将有序数组转换为二叉搜索树

取中点作为根节点，递归构建左子树和右子树

证明：满足任何一个节点的左右子树高度查不超过1

树的高度是树 - 图1

  1. 对于根节点，一次划分后，左右两边的子树高度差 <= 1

假设左子树有m个节点，右子树有m+1个节点。

左子树的高度是树 - 图2,右子树的高度是树 - 图3

证：树 - 图4

树 - 图5

所以两边高度查 < 1

class Solution {
   public TreeNode sortedArrayToBST(int[] nums) {
       //取中点作为根节点，递归构建左子树和右子树

      return recur(nums, 0, nums.length - 1);
   }

   TreeNode recur(int[] nums, int l, int r){
       if (l > r) return null;
       int mid = l + r >> 1;
       TreeNode root = new TreeNode(nums[mid]);
       root.left = recur(nums, l , mid - 1);
       root.right = recur(nums, mid + 1, r);
       return root;
   }
}

分治

分治 前序+中序构建二叉树18. 重建二叉树 - AcWing题库

重建二叉树，根本在于建立一个hashMap，存放中序遍历的下标和点的位置。这样我们就知道了左子树和右子树的范围

/** 
 * Definition for a binary tree node.
 * class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int[] preorder, inorder;
    HashMap<Integer, Integer> hash;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder; this.inorder = inorder;
        //重建二叉树，根本在于建立一个hashMap，存放中序遍历的下标和点的位置。这样我们就知道了左子树和右子树的范围
        hash = new HashMap<Integer, Integer>();
        for (int i = 0; i < inorder.length; i ++) hash.put(inorder[i] , i);
        return dfs(0, preorder.length - 1, 0, inorder.length - 1);
    }
     public TreeNode dfs(int pl, int pr, int il, int ir){
        if (pl > pr) return null; 
        TreeNode root = new TreeNode(preorder[pl]);
        int idx = hash.get(root.val);
        //左子树对应的前序遍历和中序遍历范围
        root.left = dfs(pl + 1, pl + idx - il, il, idx - 1);
        root.right = dfs(pl + idx - il + 1, pr, idx + 1, ir);
        return root;
     }
}

分治46. 二叉搜索树的后序遍历序列 - AcWing题库

思路

由于后序遍历，根节点一定是数组的最后一个元素

二叉搜索树规定了左子树的值都要比root小；右子树的值都比root大

因此，通过递归来判断子树的正确性。

定义根节点的索引是j，[i,j]表示区间 [i,j]可以成为一棵树

  1. 遍历数组节点，找到一个 > j的节点下标 m， [i, m - 1] 就是 j 的左子树 ； [m, j - 1]就是j的右子树。

  2. 遍历判断右区间是否满足 > j的性质

    • 如果满足继续向下分治子树
    • 不满足，说明不能组成二叉搜索树
class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }

    public boolean recur(int[] a, int i, int j){
        if (i >= j) return true;
        //找到划分区间点m
        int p = i;
        while (a[p] < a[j]) p++;
        //判断右区间的正确性
        int m = p;
        while (a[p] > a[j]) p++;
        return p == j && recur(a, i, m - 1) && recur(a, m, j - 1);
    }
}

树的宽搜

层次遍历 树的宽搜43. 不分行从上往下打印二叉树 - AcWing题库

思路

按照前序遍历递归每个点，如果左右子节点不为空，将其左右子节点添加到list

不能使用前序遍历（深搜），要使用宽搜

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<Integer> res = new ArrayList<Integer>();
    Deque<TreeNode> list = new LinkedList<TreeNode>();

    public List<Integer> printFromTopToBottom(TreeNode root) {
        if (root == null) return res;
        list.addLast(root); res.add(root.val);
        while (!list.isEmpty()){
            TreeNode t = list.pollFirst();
            if (t.left != null) {
                list.add(t.left);
                res.add(t.left.val);
            }
            if (t.right != null){
                list.add(t.right);
                res.add(t.right.val);
            } 
        }
        return res;
    }
}

加入判断条件的宽搜 44. 分行从上往下打印二叉树 - AcWing题库

思路

和上一题相似。

额外设定：

level 同一层的节点数组 q 宽搜队列 res结果数组

在list中加入null代表一层的末尾，两个null之间是同一层元素

  • 进行遍历：

    • 如果没有遍历到null，将节点的左右子节点（下一层节点）加入q，将当前节点加入level
    • 当遍历到null的时候，代表一层节点遍历结束，都加入level中了（也代表下一层节点都加入q中）。清空level，插入null作为下一层的结尾点。将level插入res中，表示当前层的节点
class Solution {
    public List<List<Integer>> printFromTopToBottom(TreeNode root) {
        List<Integer> level = new ArrayList<Integer>();
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Deque<TreeNode> q = new LinkedList<TreeNode>();

        if (root == null) return res;
        q.addLast(root);
        q.addLast(null);
        while (q.size() > 0){
            TreeNode t = q.pollFirst();
            if (t != null){
                //把下一层节点加入q中
                if (t.left != null) q.addLast(t.left);
                if (t.right != null) q.addLast(t.right);
                //把当前节点加入level中
                level.add(t.val);
            }else{
                //如果level为空，代表当前层没有节点，走到了树末尾
                if (level.size() == 0) break;
                res.add(new ArrayList<Integer>(level));
                level.clear();
                q.addLast(null);
            }
        }
        return res;
    }
}

宽搜 45. 之字形打印二叉树 - AcWing题库

思路

添加一个变量，根据当前层的不同决定是否将level反转

class Solution {
    public List<List<Integer>> printFromTopToBottom(TreeNode root) {
        List<Integer> level = new ArrayList<Integer>();
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Deque<TreeNode> q = new LinkedList<TreeNode>();

        boolean isRev = false;
        if (root == null) return res;
        q.addLast(root);
        q.addLast(null);
        while (q.size() > 0){
            TreeNode t = q.pollFirst();
            if (t != null){
                //把下一层节点加入q中
                if (t.left != null) q.addLast(t.left);
                if (t.right != null) q.addLast(t.right);
                //把当前节点加入level中
                level.add(t.val);
            }else{
                //如果level为空，代表当前层没有节点，走到了树末尾
                if (level.size() == 0) break;
                //根据当前层数来反转level
                if (isRev) Collections.reverse(level);
                isRev = !isRev;
                res.add(new ArrayList<Integer>(level));
                level.clear();
                q.addLast(null);
            }
        }
        return res;
    }
}

分行宽搜 / 116. 填充每个节点的下一个右侧节点指针

class Solution {
    public Node connect(Node root) {
        //进行层次遍历，把每一层的节点都放入Queue，然后把Queue中一层的节点后设置next
        Queue<Node> q = new LinkedList<Node>();
        List<List<Node>> res = new ArrayList<List<Node>>();
        List<Node> level = new ArrayList<Node>();
        if (root == null) return null;
        q.add(root);
        q.add(null);
        while (!q.isEmpty()){
            Node t = q.poll();
            level.add(t);
            if (t == null){
                if (q.size() > 0) q.add(null);
                res.add(new ArrayList<Node>(level));
                level.clear();
                continue;
            }
            if (t.left != null)
                q.add(t.left);
            if (t.right != null)
                q.add(t.right);
        }
        //拿出res

        for (List<Node> c : res){
            Node pre = null, cur = null;
            for (Node e : c){
                cur = e;
                if (pre != null)
                    pre.next = cur;
                pre = cur;
            }
            System.out.println();
        }
        return root;
    }
}

由于题目中每一层末尾节点的next为null，因此不需要队列存放每一层了

从每一层的左节点开始（由于是完美二叉树，左节点不存在就代表所有层都遍历完了），遍历每一层，处理

root.left.next = root.right;

if(root.rigjht != null)

root.right.next = root.next.left;

class Solution {
    public Node connect(Node root) {
        if (root == null) return null;
        Node res = root;
        //root不进入最后一层
        while (root.left != null){
            //遍历每一层
            for (Node p = root; p != null; p = p.next){
                p.left.next = p.right;
                //由于是完美二叉树，每个节点都有两个子节点，不需要p.right 一定存在
                if (p.right != null && p.next != null) p.right.next = p.next.left;
            }
            //进入下一层
            root = root.left;
        }
        return res;
    }
}

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

class Solution {
    public Node connect(Node root) {
        if (root == null) return null;
        //由于不是完美二叉树，不能直接定义左右子树的next
        //因此定义两个虚拟节点，把一层的节点串一个链表
        Node cur = root;
        while (cur != null){
            //head,tail表示下一层的链表的首位两个节点
            //head作为虚拟节点，是下一层的入口
            Node head = new Node(-1);
            Node tail = head;
            for (Node p = cur; p != null; p = p.next){
                if (p.left != null) tail = tail.next = p.left;
                if (p.right != null) tail = tail.next = p.right;
            }
            //进入下一层的入口
            cur = head.next;
        }
        return root;
    }
}

特殊情况

两种情况的实现19. 二叉树的下一个节点 - AcWing题库

树 - 图6%0A#card=math&code=o%28h%29%0A)

一共有两种情况：

  1. 当前点有右子节点，那么，下一个点就是右子节点的最左端（如果右子节点没有左子节点，就返回 右子节点本身）

  2. 如果当前点没有右子节点，就要返回当前节点的第一个拐点

    也就是这个点的祖父节点，这个祖父节点是其父节点的左子节点

提供了father的节点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode father;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode inorderSuccessor(TreeNode p) {
        if (p.right != null){
            p = p.right;
            while (p.left != null) p = p.left;
            return p;
        }
        else{
            while (p.father != null && p == p.father.right){
                p = p.father;
            }
            return p.father;
        }
    }
}

树和其他数据结构转换

中序遍历递归+pre节点运用/ 递归返回首尾节点49. 二叉搜索树与双向链表

思路

二叉搜索树 转 双向链表，需要将每个树中的每个节点的 left，right指针指向对应搜索树的节点。

对每个root进行递归处理，返回由root为根节点的子树转换成的双向链表的两端节点。

对root的左子节点进行处理，返回：

{root的左子树的最左侧（左子树最小的点）l.l、root的左子树的最右侧（左子树最大的点）l.r}

对root的右子节点进行处理，返回：

{root的右子树的最左侧（右子树最小的点）r.l 、root的右子树的最右侧（左子树最大的点）r.r}

其中 left 指向 l.r,right 指向 r.l。 这两个点的值是root的左邻、右邻值。

并且 l.l是链表的最左节点， r.r是链表的最右节点。

因此返回 {l.l, r.r}

此时还要细分四种情况：

  1. root 没有左右子节点。直接返回 {root, root}，因为root不用再细分了
  2. root 有左右子节点, 连接root.left, root.right。 返回 {l.l ,r.r},代表root的双向链表中两侧节点。
  3. root只有左子节点, 连接root.left。{l.l, root}代表链表的左右端点
  4. root只有右子节点, 连接root.right。{root, r.r}代表链表的左右端点
class Solution {
    public TreeNode convert(TreeNode root) {
        //判断空的情况
        if (root == null) return null;
        ArrayList<TreeNode> res = recur(root);
        return res.get(0);
    }

    public ArrayList<TreeNode> recur(TreeNode root){
        ArrayList<TreeNode> t = new ArrayList<TreeNode>();
        //`root` 没有左右子节点。
        if (root.left == null && root.right == null) {
            //直接返回 `{root, root}`，因为root不用再细分了
            t.add(root); t.add(root);
            return t;
        }
        //`root` 有左右子节点 
        if (root.left != null && root.right != null){
            ArrayList<TreeNode> lSides = recur(root.left);
            ArrayList<TreeNode> rSides = recur(root.right);
            //连接`root.left, root.right`
            root.left = lSides.get(1); lSides.get(1).right = root;
            root.right = rSides.get(0); rSides.get(0).left = root;
            //返回 `{l.l ,r.r}`,代表root的双向链表中两侧节点。
            t.add(lSides.get(0));t.add(rSides.get(1));
            return t;
        }
        //`root`只有左子节点
        if (root.left != null){
            //连接root.left
            ArrayList<TreeNode> lSides = recur(root.left);
            root.left = lSides.get(1); lSides.get(1).right = root;
            //`{l.l, root}`代表链表的左右端点
             t.add(lSides.get(0));t.add(root);
            return t;
        }
        //`root`只有右子节点
        if (root.right != null){
            //连接root.right
            ArrayList<TreeNode> rSides = recur(root.right);
            root.right = rSides.get(0); rSides.get(0).left = root;
            //`{root, r.r}`代表链表的左右端点
             t.add(root);t.add(rSides.get(1));
            return t;
        }
        return t;
    }
}

更简单的思路

中序遍历+pre,head双向链表转换

利用中序遍历得到有序节点的特性

  1. 进行中序遍历

    • 如果是首节点（pre == null），设置head
    • 不是首节点，将其和pre双向连接起来
  2. 更新 pre = root
class Solution {
    TreeNode pre, head;
    public TreeNode convert(TreeNode root) {
        if (root == null) return null;
        dfs(root);
        return head;
    }
    public void dfs(TreeNode root){
        if (root == null) return ;
        dfs(root.left);
        if (pre == null){
            head = root;
        }
        else{
            pre.right = root;
            root.left = pre;
        }
        pre = root;
        dfs(root.right);
    }
}

树和字符串的相互转换 50. 序列化二叉树

使用前序遍历构造字符串，并且前序遍历将字符串转换回树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    String res = "";
    int idx = 0;
    // Encodes a tree to a single string.
    String serialize(TreeNode root) {
        //使用前序遍历
        preOrder(root);
        //System.out.println(res);
        return res;
    }

    public void preOrder(TreeNode root){
        //遇到null，字符串中添加null
        if (root == null){
            res += "null ";
            return ;
        }
        res += String.valueOf(root.val);
        res += " ";
        preOrder(root.left);
        preOrder(root.right);
    }

    // Decodes your encoded data to tree.
    TreeNode deserialize(String data) {
        //前序遍历构造树,idx表示字符下标，用于得到节点的值或者null字符
        return preToString(data);
    }
    public TreeNode preToString(String data){
        //idx1表示下一个节点的起始空格
        int idx1 = idx;
        while(data.charAt(idx1) != ' ') idx1++;
        //如果当前节点是null,idx跳到下一个节点的起始字符（空格+1），返回节点为null
        if (data.charAt(idx) == 'n'){
            idx = idx1 + 1;
            return null;
        }
        //如果节点不是null，得到节点的value
        else{
            int value = 0, sign = 1;
            //特判负数
            if (data.charAt(idx) == '-'){
                idx ++;
                sign = -1;
            }
            for (int i = idx; i < idx1; i ++){
                value = value * 10 + data.charAt(i) - '0';
            }
            value *= sign;
            //idx跳到下一个节点的起始字符
            idx = idx1 + 1;
            //创建对应值得节点
            TreeNode root = new TreeNode(value);
            //前序遍历构造树
            root.left = preToString(data);
            root.right = preToString(data);
            return root;
        }
    }
}