算法必读 1 学习算法和刷题的思路指南

数据结构存储方式

• 顺序存储

• 链式存储

  数据结构基本操作

• 遍历 + 访问

• 增
• 删
• 改

• 查

  框架

• 遍历

  • 数组

    void traverse(int[] arr) {
    for(int i = 0; i < arr.length; i++) {
       // 访问arr[i]
    }
    }

  • 链表(迭代 + 递归)

    • 迭代

      void traverse(ListNode head) {
      for(ListNode p = head; p != null; p = p.next) {
      // 访问 p.val
      }
      }
      

    • 递归

      void traverse(ListNode head) {
      // 访问 head.val
      traverse(head.next);
      }
      

• 二叉树遍历（递归）

  void traverse(TreeNode root) {
    traverse(root.left);
    traverse(root.right);
  }
  

• N 叉树遍历(递归)

  void traverse(TreeNode root) {
    for(TreeNode child: root.children) {
        traverse(child);
    }
  }
  

二叉树练习

• LeetCode 124 - Hard- 求二叉树最大路径和

    int oneMaxSide(TreeNode root) {
        if(root == null) {
            return 0;
        }
  
        // 左右 子树 路径 小于0，就不选择，就是0
        int left = Math.max(0, oneMaxSide(root.left));
        int right = Math.max(0, oneMaxSide(root.right));
        // 计算 以 root 为根结点的 最大路径
        int ans = left + right + root.val;
        if(maxans < ans) maxans = ans;
        // 经过该点的话， 只能选择 root 左子树，或者右子树， 选择大的
        return Math.max(left, right) + root.val;
    }
  

• LeetCode 99 - Hard- 恢复二叉树搜索树

  • 中序遍历，记录排错的位置，再交换

    public void inOrder(TreeNode root) {
       if(root == null) return;
    
       inOrder(root.left);
       // 最 左边的时候 pre == null, 不处理
       if(pre != null && pre.val > root.val) {
           if(t1 == null) t1 = pre;
           t2 = root;
       }
    
       pre = root;
       inOrder(root.right);
    }