LC树题目分类详解

作者: Aaron_Swartz | 来源:发表于2019-10-03 16:16 被阅读0次

LC树题目分类详解
LC链表题目分类详解
LC数组题目分类详解
高级数据结构(1)-线段树
Python数据分析与机器学习39-Xgboost算法实例
70. Climbing Stairs
音视频:AAC
决策树是什么东东？
iOS 题目详解部分一
[Leetcode208](python):Trie树的基本操作

leetcode 98 验证二叉排序树的递归写法

// 至今尚未弄懂的递归写法
public class Solution98 {
   // 全局变量
   Integer last = - Integer.MAX_VALUE;
   
   public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (isValidBST(root.left)) {
            if (last < root.val) {
                last = root.val;
                System.out.println("root: " + root.val + "  " + "last: " + last);
                return isValidBST(root.right);
            }
        }
        return false;
    }

// 相对简单一些的递归写法
    public boolean isValidBST(TreeNode root) {
        return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    public boolean helper (TreeNode root, long min, long max) {  // 基本数据类型比较的时候会自动转换
        if (root == null) return true;
        if (root.val <= min || root.val >= max) return false;
        // 每次递归下去的是当前子树中所有节点的最大最小值。
        return helper(root.left, min, root.val) && helper(root.right, root.val, max);
    }

// 自己根据二叉树排序树中序遍历顺序写的
class Solution {
    // 2 中序遍历为严格递增序列
    private List<Integer> ans = new ArrayList<Integer>();
    
    public boolean isValidBST(TreeNode root) {
        helper(root);
        if (ans.isEmpty() || ans.size() == 1) return true;
        Boolean flag = false;
        for (int i = 0;i < ans.size() - 1; ++i) {
            if (ans.get(i + 1) <= ans.get(i)) return false; 
        }
        return true;
    }
    
    // 中序遍历二叉树
    public void helper (TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            helper(root.left);
        }
        ans.add(root.val);
        if (root.right != null) {
            helper(root.right);
        }
    }
}

leetcode 101 树的镜像对称判断

// 执行时间：1ms 消耗内存：38.1M
// 代码繁琐
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) {
            return true;
        }
        if (root.left == null || root.right == null) {
             return false;
        }
        return helper(root.left, root.right);
    }
    
    public boolean helper (TreeNode p, TreeNode q) {
        // 临界条件
        if (p == null && q == null) {
            return true;
        }
        if (p != null && q != null) {
            if (p.val != q.val) {
                 return false;
            }
        }
        if ((p != null && q == null) || (p == null && q != null)) {
            return false;
        }
        // 递归前进
        return helper(p.left, q.right) && helper(p.right, q.left);
    }
}

网上解答思路
递归结束条件：
1 都为空指针返回true
2 只有一个空指针返回fasle、
递归过程
1 判断两个指针当前节点值是否相等
2 判断A的右子树与B的左子树是否对称
3 判断A的左子树与B的右子树是否对称

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

102 二叉树的层次遍历

// AC时间过长，大概30min，不符合面试要求
// 首先应该明确这个肯定是两层循环。
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Queue<TreeNode> tempQueue = new LinkedList<>();
            List<Integer> ans = new ArrayList<>();
            while (!queue.isEmpty()) {
               TreeNode temp = queue.poll();
                ans.add(temp.val);
                if (temp.left != null) tempQueue.add(temp.left);
                if (temp.right != null) tempQueue.add(temp.right);
            }
            res.add(ans);
            queue = tempQueue;
        }
        return res;
    }
}

其实本质思想就是两层，可以用两个链表或者队列替换链表来实现。一层存储当前层节点，一层存储下一层节点。

103 二叉树的锯齿遍历
解法一：

// j网上C++ 实现的一个算法，其实本质就是层次遍历，不过是用标记位来表示那一层是需要翻转的。
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>>ans;
        if(root==NULL)return ans;
        queue<TreeNode *>q;
        q.push(root);
        int flag=1;
        while(!q.empty()){
            queue<TreeNode *>qt;
            vector<int>res;
            while(!q.empty()){
                TreeNode *t=q.front();q.pop();
                res.push_back(t->val);
                if(t->left)qt.push(t->left);
                if(t->right)qt.push(t->right);
            }
            if(flag<0)reverse(res.begin(),res.end());
            flag=-flag;//标志是否需要反转
            ans.push_back(res);
            q=qt;
        }
        return ans;
    }
};

解法二：使用java 双端队列解决

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null)
            return new ArrayList<>();
        List<List<Integer>> res = new LinkedList<>();
        Deque<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean left = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            LinkedList<Integer> list = new LinkedList<>();
            while (size-- > 0) {
                TreeNode node = queue.removeFirst();
                if (node != null) {
                    if(node.left != null)
                        queue.addLast(node.left);
                    if(node.right != null)
                        queue.addLast(node.right);
                    if (left)
                        list.addLast(node.val);
                    else
                        list.addFirst(node.val);
                }
            }
            res.add(list);
            left = !left;
        }
        return res;
    }
}

解法三：也是最好想的，直接用双stack方法来解决

// 最后费劲九牛二虎之力的双stack解法
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        Stack<TreeNode> stack1 = new Stack<>(); // 正向记录
        Stack<TreeNode> stack2 = new Stack<>(); // 反向记录
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        stack1.add(root);
        while (true) {
            List<Integer> ans = new ArrayList<>();
            while (!stack1.isEmpty()) {
                TreeNode temp = stack1.pop();
                ans.add(temp.val);
                if (temp.left != null) stack2.add(temp.left);
                if (temp.right != null) stack2.add(temp.right);
            }
            if (!ans.isEmpty()) {
                res.add(new ArrayList(ans));
                ans.clear();
            } else {
              break;  
            }
            
            while (!stack2.isEmpty()) {
                TreeNode temp = stack2.pop();
                ans.add(temp.val);
                if (temp.right != null) stack1.add(temp.right);
                if (temp.left != null) stack1.add(temp.left);    
            }
            if (!ans.isEmpty()) {
                res.add(new ArrayList(ans));
                ans.clear();
            } else {
              break;  
            }
        }
        return res;
    }
}

我的错误解法: 本以为两个队列可以解决，但是其实从逻辑上就应该明白是错误的，两个队列类似于两个链表，还是没有翻转判断的条件，所以显然仅仅这样是解决不了的！！！

// 注意: 这部分代码为错误代码
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        // 双Queue
        Queue<TreeNode> queue1 = new LinkedList<>(); // 正向记录
        Queue<TreeNode> queue2 = new LinkedList<>(); // 反向记录
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        queue1.add(root);
        while (true) {
            List<Integer> ans = new ArrayList<>();
            while (!queue1.isEmpty()) {
                TreeNode temp = queue1.poll();
                ans.add(temp.val);
                if (temp.right != null) queue2.add(temp.right);
                if (temp.left != null) queue2.add(temp.left);    
            }
            if (!ans.isEmpty()) {
                res.add(new ArrayList(ans));
                ans.clear();
            } else {
              break;  
            }
            
            while (!queue2.isEmpty()) {
                TreeNode temp = queue2.poll();
                ans.add(temp.val);
                if (temp.left != null) queue1.add(temp.left);    
                if (temp.right != null) queue1.add(temp.right);
            }
            if (!ans.isEmpty()) {
                res.add(new ArrayList(ans));
                ans.clear();
            } else {
              break;  
            }
        }
        return res;
    }
}

leetcode 110 平衡二叉树判断

// 我的解法, 时间通过, 但是内存消耗过多
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return (Math.abs(leftDepth - rightDepth) <= 1) && isBalanced(root.left) && isBalanced(root.right);
    }
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

// leetcode 上一个解法
class Solution {
    public boolean isBalanced(TreeNode root) {
        return depth(root) != -1;
    }

    private int depth(TreeNode root) {
        if (root == null) return 0;
        int left = depth(root.left);
        if(left == -1) return -1;  // 这里返回-1其实就是在递归中某个结点已经不满足结果，因此已经终止迭代。
        int right = depth(root.right);
        if(right == -1) return -1;
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }
}

执行用时 :1 ms, 内存消耗 :38.6 MB

显然第二个代码内存消耗更少些，本质就是在实际递归过程中，遇到不满足条件的及时返回-1，终止递归继续进行。

111 二叉树的最小深度: 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

临界条件如下：
叶子节点的定义是左孩子和右孩子都为 null 时叫做叶子节点
当 root 节点左右孩子都为空时，返回 1
当 root 节点左右孩子有一个为空时，返回不为空的孩子节点的深度
当 root 节点左右孩子都不为空时，返回左右孩子较小深度的节点值
这道题目本质上还是要搞清楚临界条件为三种

// 在大神提示了临界条件的基础上写出来的一版
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        if (root.left == null) {
            return 1 + minDepth(root.right);
        }
        if (root.right == null) {
            return 1 + minDepth(root.left);    
        }
        return 1 + Math.min(minDepth(root.left), minDepth(root.right)); 
    }
}

// 网上解法
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        //这道题递归条件里分为三种情况
        //1.左孩子和有孩子都为空的情况，说明到达了叶子节点，直接返回1即可
        if(root.left == null && root.right == null) return 1;
        //2.如果左孩子和由孩子其中一个为空，那么需要返回比较大的那个孩子的深度        
        int m1 = minDepth(root.left);
        int m2 = minDepth(root.right);
        //这里其中一个节点为空，说明m1和m2有一个必然为0，所以可以返回m1 + m2 + 1;
        if(root.left == null || root.right == null) return m1 + m2 + 1;
        
        //3.最后一种情况，也就是左右孩子都不为空，返回最小深度+1即可
        return Math.min(m1,m2) + 1; 
    }
}

112 leetcode: 路径总和问题

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
       // 1 这个临界条件的意思是当前节点已经为空了，但是在此之前还没有true的返回，则直接返回false
        if (root == null) {
            return false;
        }
        // 2 叶子结点的临界条件
        if (root.left == null && root.right == null) {
            return sum == root.val;
        }
        int ret = sum - root.val;
        // if (root.left == null) { 这部分可以直接注释掉是因为root == null 满足就直接返回false了。
        //     return hasPathSum(root.right, ret);
        // }
        // if (root.right == null) {
        //     return hasPathSum(root.left, ret);
        // }
        return hasPathSum(root.right, ret) || hasPathSum(root.left, ret);
    }
}

// 网上解法一
public boolean hasPathSum(TreeNode root, int sum) {
      return  helper(root,0,sum);
    }
    public boolean helper(TreeNode root,int cur,int sum)
    {
      if(root==null)
          return false;
        cur=cur+root.val;
        if(root.left==null&&root.right==null)
        {
            return cur==sum;
        }else
        {
            return helper(root.left,cur,sum)|| helper(root.right,cur,sum);
        }
    }

113 路径总和II：给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

// 自己的解法，在迭代的时候，每次需要额外的开销，新建ArrayList，显然是不合适的，虽然通过
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList();
        helper(res, new ArrayList(), root, sum);
        return res;
    }

    public void helper (List<List<Integer>> res, List<Integer> array, TreeNode root, int sum) {
        // 临界条件
        if (root == null) {
            array = null;
            return;
        }        
        array.add(root.val);
        if (root.left == null && root.right == null && sum == root.val) {
            res.add(array);
            return;
        }
        helper(res, new ArrayList(array), root.left, sum - root.val); // 主要是这一步
        helper(res, new ArrayList(array), root.right, sum - root.val);
    }
}
消耗
内存：42.6MB 空间复杂度过大
耗时：3ms

// 网上同学的解法
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> ans = new ArrayList<>();

        helper(root, sum, ans, new ArrayList<>());

        return ans;
    }

    private void helper(TreeNode node, int sum, List<List<Integer>> ans, List<Integer> path) {
        if (node == null) {
            return;
        }

        // 将沿途到节点加入到path中
        sum -= node.val;
        path.add(node.val);

        // 遍历到叶节点
        if (node.left == null && node.right == null) {
            // 如果这是一条可行的路径，才复制path的结果到ans
            if (sum == 0)
                ans.add(new ArrayList<>(path));
        } else {
            helper(node.left, sum, ans, path);
            helper(node.right, sum, ans, path);
        }

        // 回溯
        path.remove(path.size() - 1);
    }
}

// 我参考网上之后的最后一版解法
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList();
        helper(res, new ArrayList(), root, sum);
        return res;
    }
    
    public void helper (List<List<Integer>> res, List<Integer> array, TreeNode root, int sum) {
        // 临界条件
        if (root == null) {
            return;
        }        
        array.add(root.val);
        if (root.left == null && root.right == null) {
            if (sum == root.val) {
                res.add(new ArrayList(array));
                // return;  *** 这个return 当时是我多加的，后来发现不合适需要去掉 ***
            }
        } else {
            helper(res, array, root.left, sum - root.val);
            helper(res, array, root.right, sum - root.val);
        }
        // 回溯
        array.remove(array.size() - 1);
    }
}
执行时间：2ms
消耗内存：37.7M
优化成功

这里需要注意一个节点需要回溯的条件：
先判断当前节点是否为叶子节点，如果是则进入处理逻辑。如果不是叶子节点，则需要分别进入该节点的左右子叶节点中递归调用处理。当处理完这个之后，整个节点的也就处理完了，如果有符合要求的路径一定是加入了，然后就可以执行回溯操作。

226 翻转二叉树
- 递归解答

class Solution {
    public TreeNode invertTree(TreeNode root) {
        // 递归边界
        if ((root == null) || (root.left == null && root.right == null)) return root;
        // 取出标记节点的值
        TreeNode left = root.left;
        TreeNode right = root.right;
        // 递归前进
        root.left = invertTree(right);
        root.right = invertTree(left);
        return root;
    }
}

迭代解答: 层次遍历加上途中交换左右子树

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    // LinkedList实现了集合框架的Queue接口
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root); // 加入元素
    while (!queue.isEmpty()) {
      // 获取并移出元素
      TreeNode current = queue.poll();
      //交换左右子树
      TreeNode temp = current.left;
      current.left = current.right;
      current.right = temp;
      //左子树不为空，将左子树入栈
      if (current.left != null) queue.add(current.left);
      //右子树不为空，将右子树入栈
      if (current.right != null) queue.add(current.right);
    }
    return root;
}

leetcode 236 二叉树的最近公共祖先：面试的时候遇见过一次
- 父指针迭代法：本质就是依次记录节点的父指针，然后比较两个节点父指针的交点。

class Solution {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        // Stack for tree traversal
        Deque<TreeNode> stack = new ArrayDeque<>();

        // HashMap for parent pointers
        Map<TreeNode, TreeNode> parent = new HashMap<>();

        parent.put(root, null);
        stack.push(root);

        // Iterate until we find both the nodes p and q
        while (!parent.containsKey(p) || !parent.containsKey(q)) {

            TreeNode node = stack.pop();

            // While traversing the tree, keep saving the parent pointers.
            if (node.left != null) {
                parent.put(node.left, node);
                stack.push(node.left);
            }
            if (node.right != null) {
                parent.put(node.right, node);
                stack.push(node.right);
            }
        }

        // Ancestors set() for node p.
        Set<TreeNode> ancestors = new HashSet<>();

        // Process all ancestors for node p using parent pointers.
        while (p != null) {
            ancestors.add(p);
            p = parent.get(p);
        }

        // The first ancestor of q which appears in
        // p's ancestor set() is their lowest common ancestor.
        while (!ancestors.contains(q))
            q = parent.get(q);
        return q;
    }
}
时间复杂度：O(N)
空间复杂度：O(N)

显然运行效率一般

递归法: 引入mid变量

class Solution {

    private TreeNode ans;

    public Solution() {
        // Variable to store LCA node.
        this.ans = null;
    }

    private boolean recurseTree(TreeNode currentNode, TreeNode p, TreeNode q) {

        // If reached the end of a branch, return false.
        if (currentNode == null) {
            return false;
        }

        // Left Recursion. If left recursion returns true, set left = 1 else 0
        int left = this.recurseTree(currentNode.left, p, q) ? 1 : 0;

        // Right Recursion
        int right = this.recurseTree(currentNode.right, p, q) ? 1 : 0;

        // If the current node is one of p or q
        int mid = (currentNode == p || currentNode == q) ? 1 : 0;


        // If any two of the flags left, right or mid become True
        if (mid + left + right >= 2) {
            this.ans = currentNode;
        }

        // Return true if any one of the three bool values is True.
        return (mid + left + right > 0);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Traverse the tree
        this.recurseTree(root, p, q);
        return this.ans;
    }
}

比较简单的递归写法

本质中是在左右子树种寻找p，q节点，如果左右子树中均存在目标节点，则说明root节点为最近公共祖先。否则在左子树递归寻找p,q节点，要么为null，要么找到该节点。

   public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 临界条件
        if (root == null || root == q || root == p) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) return root;
        return left != null ? left : right;
    }

leetcode 235: 单链表plus 1

/**
 * 2019/10/6.
 * 单链表加1
 * 756 plus 1
 *
 */
public class Solution23 {
    public ListNode plusOne(ListNode root) {
        if (root == null) {
            return root;
        }
        int flag = helper(root);
        if (flag == 1) {
            ListNode node = new ListNode(1);
            node.next = root;
            return node;
        }
        return root;
    }

    public int helper(ListNode root) {
        // 临界条件
        if (root == null) return 1; // 这里表示最后加1的情形
        int sum = (helper(root.next) + root.value);
        int flag = sum / 10;
        root.value = sum % 10;
        return flag;
    }

之前面试过的题目，重新AC了一遍

LC树题目分类详解
leetcode 98 验证二叉排序树的递归写法 leetcode 101 树的镜像对称判断网上解答思路递归结束...
LC链表题目分类详解
基础知识链表翻转实际应用1 LeetCode] Plus One Linked List 链表加一运算如何在...
LC数组题目分类详解
leetcode 169 求众数下面代码给出：哈希法/排序法/投票法哈希法：用map统计个数，直接计算即可排序...
高级数据结构(1)-线段树
这应该是系统介绍LC的线段树题目全网截止发文时最全的文章了。从这篇文章里，你可以学到如何用线段树思维和模板解LC的...
Python数据分析与机器学习39-Xgboost算法实例
一. xgboost.XGBClassifier 分类算法参数详解语法: booster gbtree 树模型...
70. Climbing Stairs
LC最简单的题目？
音视频:AAC
aac相关 aac分类按profile分类：lc，ld，he按封装格式分类：adts，adif，latm
决策树是什么东东？
小白自学路上的备忘记录。。。参考：决策树(分类树、回归树)决策树:这个博客的图真好看，通俗易懂。哈哈决策树详解 ...
iOS 题目详解部分一
主要记录一些题目所关联的知识点, 详解 iOS 题目详解部分一iOS 题目详解部分二iOS 题目详解部...
[Leetcode208](python):Trie树的基本操作
1. 题目来源分类：字典树 Leetcode208:Trie树的基本操作 2. 题目描述实现一个 Trie (...