二叉树 | Men的博客

二叉树的前中后序遍历

void traverse(TreeNode root) {
    // 前序遍历
    traverse(root.left)
    // 中序遍历
    traverse(root.right)
    // 后序遍历
}
非递归前序遍历
void preorder(TreeNode *root, vector<int>& res)
{
    stack< pair<TreeNode*, bool> > s;
    s.push(make_pair(root, false));
    bool visited;
    while(!s.empty()) {
        root = s.top().first;
        visited = s.top().second;
        s.pop();
        if(root == NULL) {
            continue;
        }
        if(visited) {
            res.push_back(root->val);
        } else {
            // 后序遍历
            s.push(make_pair(root->right, false));
            // 中序遍历
            s.push(make_pair(root->left, false));
            // 前序遍历
            s.push(make_pair(root, true));
        }
    }
}

二叉树的广度优先搜索（从上到下打印二叉树）

本质上是前序遍历，用一个队列存储二叉树的（先入先出）
public int[] levelOrder(TreeNode root) {
    if(root == null) return new int[0];
    Queue<TreeNode> queue = new LinkedList<>(){{ add(root); }};
    ArrayList<Integer> ans = new ArrayList<>();
    while(!queue.isEmpty()) {
        TreeNode node = queue.poll();
        ans.add(node.val);
        if(node.left != null) queue.add(node.left);
        if(node.right != null) queue.add(node.right);
    }
    int[] res = new int[ans.size()];
    for(int i = 0; i < ans.size(); i++)
        res[i] = ans.get(i);
    return res;
}

二叉树的深度优先搜索

本质上是二叉树的后续遍历，用栈存储（先入后出）
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
    ArrayList<Integer> lists=new ArrayList<Integer>();
    if(root==null)
        return lists;
    Stack<TreeNode> stack=new Stack<TreeNode>();
    stack.push(root);
    while(!stack.isEmpty()){
        TreeNode tree=stack.pop();
　　　 //先往栈中压入右节点，再压左节点，这样出栈就是先左节点后右节点了。
            if(tree.right!=null)
                stack.push(tree.right);
            if(tree.left!=null)
                stack.push(tree.left);
            lists.add(tree.val);
        }
        return lists;
    }
}

树的子结构（判断B是不是A的子结构。）

本质是二叉树的递归遍历（递归判断左右子树是不是相同）
代码步骤：A和B不能是Null，A和B相同、A的左边和B相同、A的右边和B相同
public boolean isSubStructure(TreeNode A, TreeNode B) {
      return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }
    boolean recur(TreeNode A, TreeNode B) {
        if(B == null) return true;
        if(A == null || A.val != B.val) return false;
        return recur(A.left, B.left) && recur(A.right, B.right);
    }

二叉树的镜像

本质是二叉树的递归遍历 （交换left和right）
代码步骤：判断是否是空、交换左右的遍历结果
public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        TreeNode tmp = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(tmp);
        return root;
    }
方法二：辅助栈（或队列）
利用栈（或队列）遍历树的所有节点 node ，并交换每个 node 的左 / 右子节点。
 public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        Stack<TreeNode> stack = new Stack<>() {{ add(root); }};
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if(node.left != null) stack.add(node.left);
            if(node.right != null) stack.add(node.right);
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        return root;
    }

对称二叉树

根据以上规律，考虑从顶至底递归，判断每对节点是否对称，从而判断树是否为对称二叉树
二叉树的先序遍历
// 判断左右两个数的左边和右边是不是一样，递归调用前序遍历
public boolean isSymmetric(TreeNode root) {
        //方法调用
        return isSymmetric(root,root);
    }

public boolean isSymmetric(TreeNode root1,TreeNode root2){
    if(root1 == null && root2 == null){
        return true;
    }

    //某结点只有一个子结点，故不对称，所以返回false
    if(root1 == null || root2 == null){
        return false;
    }

    //对称结点存在，但是值不相同
    if(root1.val != root2.val){
        return false;
    }

    //递归调用左子节点和右子节点
    return isSymmetric(root1.left, root2.right) && isSymmetric(root1.right,root2.left);
}

从上到下打印二叉树同一层的节点按从左到右的顺序打印

前序遍历，用队列存储每一层的值
将每一层数据存放到队列中
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }
}

从上到下打印二叉树之字形顺序打印二叉树

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
方法一：层序遍历 + 双端队列
利用双端队列的两端皆可添加元素的特性，设打印列表（双端队列），奇数层 则添加至 尾部，偶数层添加至头部
 public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            LinkedList<Integer> tmp = new LinkedList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                if(res.size() % 2 == 0) tmp.addLast(node.val); // 偶数层 -> 队列头部
                else tmp.addFirst(node.val); // 奇数层 -> 队列尾部
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }

二叉搜索树的后序

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。
每一层判断左右子树和根节点的大小关系，如果满足则继续向下判断；否则直接返回失败
递归分治 / 单调栈， 遍历顺序为 “左、右、根” 
    二叉搜索树定义： 左子树中所有节点的值 < 根节点的值；右子树中所有节点的值 > 根节点的值；其左、右子树也分别为二叉搜索树。
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }
    boolean recur(int[] postorder, int i, int j) {
        if(i >= j) return true;
        int p = i;
        while(postorder[p] < postorder[j]) p++;
        int m = p;
        while(postorder[p] > postorder[j]) p++;
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }

二叉树中和为某一值的路径

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。
前序遍历：从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
 LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>(); 
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        recur(root, sum);
        return res;
    }
    void recur(TreeNode root, int tar) {
        if(root == null) return;
        path.add(root.val);
        tar -= root.val;
        if(tar == 0 && root.left == null && root.right == null)
            res.add(new LinkedList(path));
        recur(root.left, tar);
        recur(root.right, tar);
        path.removeLast();
    }

二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
本文解法基于性质：二叉搜索树的中序遍历为 递增序列 。排序链表，双向链表。循环链表\
并在访问每个节点时构建 
cur 和前驱节点   pre 的引用指向；中序遍历完成后，最后构建头节点和尾节点的引用指向即可
中序遍历完成后，head 指向头节点， pre 指向尾节点，因此修改 
head 和  pre 的双向节点引用即可。
Node pre, head;
    public Node treeToDoublyList(Node root) {
        if(root == null) return null;
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
    void dfs(Node cur) {
        if(cur == null) return;
        dfs(cur.left);
        if(pre != null) pre.right = cur;
        else head = cur;
        cur.left = pre;
        pre = cur;
        dfs(cur.right);
    }

序列化二叉树层序遍历 BFS

定义 StringBuilder 前序遍历拼接，删除最后一个逗号
 public String serialize(TreeNode root) {
        if(root == null) return "[]";
        StringBuilder res = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(node != null) {
                res.append(node.val + ",");
                queue.add(node.left);
                queue.add(node.right);
            }
            else res.append("null,");
        }
        res.deleteCharAt(res.length() - 1);
        res.append("]");
        return res.toString();
    }

public TreeNode deserialize(String data) {
    if(data.equals("[]")) return null;
    String[] vals = data.substring(1, data.length() - 1).split(",");
    TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
    Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
    int i = 1;
    while(!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if(!vals[i].equals("null")) {
            node.left = new TreeNode(Integer.parseInt(vals[i]));
            queue.add(node.left);
        }
        i++;
        if(!vals[i].equals("null")) {
            node.right = new TreeNode(Integer.parseInt(vals[i]));
            queue.add(node.right);
        }
        i++;
    }
    return root;
}

二叉搜索树的第k大节点

第k小的话，我觉得可以反过来遍历
class Solution {
    int res, k;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }
    void dfs(TreeNode root) {
        if(root == null) return;
        dfs(root.right);
        if(k == 0) return;
        if(--k == 0) res = root.val;
        dfs(root.left);
    }
}

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

BST 的特性：BST 的中序遍历是升序序列。
通过构造 BST 的中序遍历序列，则第 k-1 个元素就是第 k 小的元素
方法一：递归
class Solution {
  public ArrayList<Integer> inorder(TreeNode root, ArrayList<Integer> arr) {
    if (root == null) return arr;
    inorder(root.left, arr);
    arr.add(root.val);
    inorder(root.right, arr);
    return arr;
  }

  public int kthSmallest(TreeNode root, int k) {
    ArrayList<Integer> nums = inorder(root, new ArrayList<Integer>());
    return nums.get(k - 1);
  }
}

二叉树的深度（后序遍历）

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
方法一：后序遍历（DFS）
  public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

方法二：层序遍历（BFS）
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        List<TreeNode> queue = new LinkedList<>() {{ add(root); }}, tmp;
        int res = 0;
        while(!queue.isEmpty()) {
            tmp = new LinkedList<>();
            for(TreeNode node : queue) {
                if(node.left != null) tmp.add(node.left);
                if(node.right != null) tmp.add(node.right);
            }
            queue = tmp;
            res++;
        }
        return res;
    }
}

二叉树的最小深度

递归，0.1，
class Solution {
  public int minDepth(TreeNode root) {
    if (root == null) {
      return 0;
    }

    if ((root.left == null) && (root.right == null)) {
      return 1;
    }

    int min_depth = Integer.MAX_VALUE;
    if (root.left != null) {
      min_depth = Math.min(minDepth(root.left), min_depth);
    }
    if (root.right != null) {
      min_depth = Math.min(minDepth(root.right), min_depth);
    }

    return min_depth + 1;
  }
}
方法2:广度优先搜索迭代
class Solution {
  public int minDepth(TreeNode root) {
    LinkedList<Pair<TreeNode, Integer>> stack = new LinkedList<>();
    if (root == null) {
      return 0;
    }
    else {
      stack.add(new Pair(root, 1));
    }

    int current_depth = 0;
    while (!stack.isEmpty()) {
      Pair<TreeNode, Integer> current = stack.poll();
      root = current.getKey();
      current_depth = current.getValue();
      if ((root.left == null) && (root.right == null)) {
        break;
      }
      if (root.left != null) {
        stack.add(new Pair(root.left, current_depth + 1));
      }
      if (root.right != null) {
        stack.add(new Pair(root.right, current_depth + 1));
      }
    }
    return current_depth;
  }
}

平衡二叉树

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
方法一：后序遍历 + 剪枝 （从底至顶）
class Solution {
    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }

private int recur(TreeNode root) {
    if (root == null) return 0;
    int left = recur(root.left);
    if(left == -1) return -1;
    int right = recur(root.right);
    if(right == -1) return -1;
    return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
}
}
方法二：先序遍历 + 判断深度 （从顶至底）
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    private int depth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }
}

二叉搜索树的最近公共祖先

用集合遍历根树，保存Hashmap
用set保存一个二叉树在集合中的结果
遍历另一个二叉树，看set中是否有，有则为最近公共祖先
方法一：迭代
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(p.val > q.val) { // 保证 p.val < q.val
            TreeNode tmp = p;
            p = q;
            q = tmp;
        }
        while(root != null) {
            if(root.val < p.val) // p,q 都在 root 的右子树中
                root = root.right; // 遍历至右子节点
            else if(root.val > q.val) // p,q 都在 root 的左子树中
                root = root.left; // 遍历至左子节点
            else break;
        }
        return root;
    }
}
方法二：递归
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val < p.val && root.val < q.val)
            return lowestCommonAncestor(root.right, p, q);
        if(root.val > p.val && root.val > q.val)
            return lowestCommonAncestor(root.left, p, q);
        return root;
    }
}

二叉树的最大宽度

最小高度树

给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。
二分，拿到中间元素，然后递归创建左右子树
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int n = nums.size();
        return createTree(nums, 0, n - 1);
    }
    TreeNode* createTree(vector<int>& nums, int start, int end) {
        if (start > end) return nullptr;
        int mid = (start + end) >> 1;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = createTree(nums, start, mid - 1);
        root->right = createTree(nums, mid + 1, end);
        return root;
    }
};

合法二叉搜索树

实现一个函数，检查一棵二叉树是否为二叉搜索树。
双百，递归遍历树，分别检查左右根节点的大小
    public boolean isValidBST(TreeNode root) {
        if(root==null) return true;
        return isValidBSThelp(root.left,Long.MIN_VALUE,root.val)&&isValidBSThelp(root.right,root.val,Long.MAX_VALUE);
    }
    private boolean isValidBSThelp(TreeNode root,long min,long max){
        if(root==null) return true;
        if(root.val<=min||root.val>=max) return false;
        boolean left = isValidBSThelp(root.left,min,root.val);
        boolean right = isValidBSThelp(root.right,root.val,max);
        return left && right;
    }

二叉树中最大路径和

给定一个非空二叉树，返回其最大路径和。
递归计算，更新max，（递归中返回较大的）
class Solution {
    int maxSum = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    maxGain(root);
    return maxSum;
}

public int maxGain(TreeNode node) {
    if (node == null) {
        return 0;
    }
    
    // 递归计算左右子节点的最大贡献值
    // 只有在最大贡献值大于 0 时，才会选取对应子节点
    int leftGain = Math.max(maxGain(node.left), 0);
    int rightGain = Math.max(maxGain(node.right), 0);

    // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
    int priceNewpath = node.val + leftGain + rightGain;

    // 更新答案
    maxSum = Math.max(maxSum, priceNewpath);

    // 返回节点的最大贡献值
    return node.val + Math.max(leftGain, rightGain);
}
}

合并二叉树

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
输入: 
    Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输出: 
合并后的树:
         3
        / \
       4   5
      / \   \ 
     5   4   7
public class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null)
            return t2;
        if (t2 == null)
            return t1;
        t1.val += t2.val;
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);
        return t1;
    }
}

翻转二叉树

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

监控二叉树

给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
根据每个节点的左右子节点来判断当前节点的状态，因此左右根后续遍历
class Solution {
public:
    //记录需要放置摄像头的数量
    int res = 0;
    int minCameraCover(TreeNode* root) 
    {
        //后序遍历，从下自上遍历。
        //若遍历至最上面，root标志为0，则多加一个摄像头
        if(dfs(root) == 0)
        {
            res++;  
        }
        return res;
    }
    int dfs(TreeNode* root)
    {

    //0：未被覆盖(当前节点未被照到)
    //1：已被覆盖(摄像头已经照到这个节点)
    //2：需放置摄像头

    //到根节点，
    if(root == NULL) return 1;
    //遍历左节点
    int left = dfs(root->left);
    //遍历右节点
    int right = dfs(root->right);
    //一个节点左右确定后，判断左右节点情况
    //所有情况00,01,02,11,12,22
    //左右孩子中有一个未被覆盖，则当前节点需要放置摄像头，当前节点标志为2
    if(left ==0 || right==0)
    {
        res++;
        return 2;
    }
    //左右孩子均为已覆盖状态,则当前节点未被覆盖，标志为0
    if(left == 1 && right == 1)
    {
        return 0;
    }
    //若左右孩子为一个覆盖一个放置了摄像头，则当前节点为已被覆盖，标志为1
    if(left+right >= 3)
    {
        return 1;
    }
    //此时已经组合完了根节点所有情况，随便返回一个整数即可
    return 0;
}
};

验证二叉树

如果一棵树是一个二叉树的话 必定除了根节点 每个非空节点的入度都为1
样例还给了某一个节点被两个"父节点"引用的例子 那这个节点的入度就为2了 也就不能构成二叉树

public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
    int[] in = new int[n];
    for (int i = 0; i < n; i++) {
        if (leftChild[i] != -1) in[leftChild[i]]++;
        if (rightChild[i] != -1) in[rightChild[i]]++;
    }

    int count0 = 0;
    int countOther = 0;
    for (int temp : in) {
        if (temp == 0) count0++;
        if (temp > 1) countOther++;
    }
    return count0 == 1 && countOther == 0;
}

最大二叉树

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。
右子树是通过数组中最大值右边部分构造出的最大二叉树。
public class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return construct(nums, 0, nums.length);
    }
    public TreeNode construct(int[] nums, int l, int r) {
        if (l == r)
            return null;
        int max_i = max(nums, l, r);
        TreeNode root = new TreeNode(nums[max_i]);
        root.left = construct(nums, l, max_i);
        root.right = construct(nums, max_i + 1, r);
        return root;
    }
    public int max(int[] nums, int l, int r) {
        int max_i = l;
        for (int i = l; i < r; i++) {
            if (nums[max_i] < nums[i])
                max_i = i;
        }
        return max_i;
    }
}

验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。
class Solution {
  public boolean helper(TreeNode node, Integer lower, Integer upper) {
    if (node == null) return true;
    int val = node.val;
    if (lower != null && val <= lower) return false;
    if (upper != null && val >= upper) return false;

    if (! helper(node.right, val, upper)) return false;
    if (! helper(node.left, lower, val)) return false;
    return true;
}

public boolean isValidBST(TreeNode root) {
    return helper(root, null, null);
  }
}

单值二叉树

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
我们先进行一次深度优先搜索，获取这颗树中的所有节点的值。然后，就可以判断所有节点的值是不是都相等了。
class Solution {
    List<Integer> vals;
    public boolean isUnivalTree(TreeNode root) {
        vals = new ArrayList();
        dfs(root);
        for (int v: vals)
            if (v != vals.get(0))
                return false;
        return true;
    }

public void dfs(TreeNode node) {
    if (node != null) {
        vals.add(node.val);
        dfs(node.left);
        dfs(node.right);
    }
}
}
方法二：递归
思路与算法
一颗树是单值的，当且仅当根节点的子节点所在的子树也是单值的，同时根节点的值与子节点的值相同。
class Solution {
    public boolean isUnivalTree(TreeNode root) {
        boolean left_correct = (root.left == null ||
                (root.val == root.left.val && isUnivalTree(root.left)));
        boolean right_correct = (root.right == null ||
                (root.val == root.right.val && isUnivalTree(root.right)));
        return left_correct && right_correct;
    }
}

二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树

          1
         / \
        2   3
       / \     
      4   5    
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
方法：深度优先搜索
首先我们知道一条路径的长度为该路径经过的节点数减一，所以求直径（即求路径长度的最大值）等效于求路径经过节点数的最大值减一。
而任意一条路径均可以被看作由某个节点为起点，从其左儿子和右儿子向下遍历的路径拼接得到。
class Solution {
    int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        ans = 1;
        depth(root);
        return ans - 1;
    }
    public int depth(TreeNode node) {
        if (node == null) return 0; // 访问到空节点了，返回0
        int L = depth(node.left); // 左儿子为根的子树的深度
        int R = depth(node.right); // 右儿子为根的子树的深度
        ans = Math.max(ans, L+R+1); // 计算d_node即L+R+1 并更新ans
        return Math.max(L, R) + 1; // 返回该节点为根的子树的深度
    }
}

二叉树的坡度

一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。
整个树的坡度就是其所有节点的坡度之和。
输入：
         1
       /   \
      2     3
输出：1
解释：
结点 2 的坡度: 0
结点 3 的坡度: 0
结点 1 的坡度: |2-3| = 1
树的坡度 : 0 + 0 + 1 = 1
方法：递归
我们需要求出该结点的左子树上所有结点和以及其右子树上全部结点和的差值。
在任何结点调用该函数，都会返回当前结点下面（包括其自身）的结点和。借助于任何结点的左右子结点的这一和值，我们可以直接获得该结点所对应的坡度。
public class Solution {
    int tilt=0;
    public int findTilt(TreeNode root) {
        traverse(root);
        return tilt;
    }
    public int traverse(TreeNode root)
    {
        if(root==null )
            return 0;
        int left=traverse(root.left);
        int right=traverse(root.right);
        tilt+=Math.abs(left-right);
        return left+right+root.val;
    }
}

恢复一棵 BST

二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。
方法一：对数组进行排序
我们直到 BST 的中序遍历是升序序列。下面展示了如何计算中序遍历。
这里被交换了两个节点，因此中序遍历是一个几乎排好序的数组，其中有两个元素被交换。识别排序数组中两个交换元素是可以在线性时间内解决的经典问题。
public int[] findTwoSwapped(List<Integer> nums) {
  int n = nums.size();
  int x = -1, y = -1;
  for(int i = 0; i < n - 1; ++i) {
    if (nums.get(i + 1) < nums.get(i)) {
      y = nums.get(i + 1);
      // first swap occurence
      if (x == -1) x = nums.get(i);
      // second swap occurence
      else break;
    }
  }
  return new int[]{x, y};
}
方法二：递归中序遍历
class Solution {
  TreeNode x = null, y = null, pred = null;

  public void swap(TreeNode a, TreeNode b) {
    int tmp = a.val;
    a.val = b.val;
    b.val = tmp;
  }

  public void findTwoSwapped(TreeNode root) {
    if (root == null) return;
    findTwoSwapped(root.left);
    if (pred != null && root.val < pred.val) {
      y = root;
      if (x == null) x = pred;
      else return;
    }
    pred = root;
    findTwoSwapped(root.right);
  }

  public void recoverTree(TreeNode root) {
    findTwoSwapped(root);
    swap(x, y);
  }
}

求二叉树中叶子节点的个数

class Solution {
    public int getLeafCount(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            // 输出叶子节点
            System.out.println("leaf nodes:" + root.val);
            return 1;
        }
        return getLeafCount(root.left) + getLeafCount(root.right);
    }
}

求二叉树第K层的节点个数

  if (level == k)
    {
        ++num;
        return num;
    }
    _FindKLevel(root->_left, k, level + 1);
    _FindKLevel(root->_right, k, level + 1);

求二叉树中最远的两个节点的距离

（1）如果具有最远距离的两个节点经过了根节点，那么最远的距离就是左边最深的深度加上右边最深的深度之和。
（2）如果具有最远距离的两个节点之间的路径不经过根节点，那么最远的距离就在根节点的其中一个子树上的两个叶子结点。

 int _Height(Node* root, int& distance)
       {
              if (root == NULL)
              {
                     return 0;
              }
              int leftH = _Height(root->_left);
              int rightH = _Height(root->_right);
              if (leftH+rightH > distance)
              {
                     distance = leftH + rightH;
              }
              return leftH > rightH ? leftH+1 : rightH+1;

二叉搜索树中的众数

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
class Solution {
    private TreeNode pre = null;
    private int[] ret;
    private int retCount = 0;
    private int maxCount = 0;
    private int currCount = 0;

public int[] findMode(TreeNode root) {
    inOrder(root);
    pre = null;
    ret = new int[retCount];
    retCount = 0;
    currCount = 0;
    inOrder(root);
    return ret;
}

private void inOrder(TreeNode root) {
    if (root == null)
        return;
    inOrder(root.left);
    if (pre != null && pre.val == root.val)
        currCount++;
    else
        currCount = 1;
    if (currCount > maxCount) {
        maxCount = currCount;
        retCount = 1;
    }
    else if (currCount == maxCount) {
        if (ret != null)
            ret[retCount] = root.val;
        retCount++;
    }
    pre = root;
    inOrder(root.right);
}
}

还原一棵二叉树

根据前序遍历和中序遍历的结果还原一棵二叉树
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

前序遍历的第一个节点是根节点，只要找到根节点在中序遍历中的位置，在根节点之前被访
问的节点都位于左子树，在根节点之后被访问的节点都位于右子树，由此可知左子树和右子树分别有多少个节点。
不要看这个函数的参数很多，只是为了控制数组索引而已，本质上该算法也就是一个前序遍历。
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>(); // 存储位置
        int length = preorder.length;
        for (int i = 0; i < length; i++) {
            indexMap.put(inorder[i], i);
        }
        TreeNode root = buildTree(preorder, 0, length - 1, inorder, 0, length - 1, indexMap);
        return root;
    }

public TreeNode buildTree(int[] preorder, int preorderStart, int preorderEnd, int[] inorder, int inorderStart, int inorderEnd, Map<Integer, Integer> indexMap) {
    if (preorderStart > preorderEnd) {
        return null;
    }
    int rootVal = preorder[preorderStart];
    TreeNode root = new TreeNode(rootVal);
    if (preorderStart == preorderEnd) {
        return root;
    } else {
        int rootIndex = indexMap.get(rootVal);
        int leftNodes = rootIndex - inorderStart, rightNodes = inorderEnd - rootIndex;
        TreeNode leftSubtree = buildTree(preorder, preorderStart + 1, preorderStart + leftNodes, inorder, inorderStart, rootIndex - 1, indexMap);
        TreeNode rightSubtree = buildTree(preorder, preorderEnd - rightNodes + 1, preorderEnd, inorder, rootIndex + 1, inorderEnd, indexMap);
        root.left = leftSubtree;
        root.right = rightSubtree;
        return root;
    }
}
}

二叉搜索树序列

从左向右遍历一个数组，通过不断将其中的元素插入树中可以逐步地生成一棵二叉搜索树。给定一个由不同节点组成的二叉搜索树，输出所有可能生成此树的数组。
给定如下二叉树

        2
       / \
      1   3
返回：

[
   [2,1,3],
   [2,3,1]
]
class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> BSTSequences(TreeNode* root) {
    
    if(root == nullptr) return {{}};

    // queue 数据结构 并不是一个好的选项 
    // queue<TreeNode*> q;  // q 用于保存 前后顺序不影响最终BST结果的 节点
    deque<TreeNode*> q;
    vector<int> path;
    q.push_back(root);

    dfs(q, path);
    return res;
}

void dfs(deque<TreeNode*>& q, vector<int>& path){
    // cout << "size of path:" << path.size() <<endl;
    if(q.empty()) {
        res.push_back(path);
        return;
    }

    int size = q.size();
    cout << "***" << q.size() << endl;
    for(int i = 0; i < size; i++){
        auto curr = q.front();
        q.pop_front();

        path.push_back(curr->val);
        if(curr && curr->left) q.push_back(curr->left);
        if(curr && curr->right) q.push_back(curr->right);
        
        dfs(q, path);

        // 回溯要保证 状态还原
        if(curr && curr->left) q.pop_back();
        if(curr && curr->right) q.pop_back();
        q.push_back(curr);
        
        path.pop_back();
    }
}
};

二叉搜索树总结

void BST(TreeNode root,int target) {
    if(root.val == target) 
        //找到目标，做点什么
    if(root.val < target) 
        BST(root.right, target);
    if(root.val > target) 
        BST(root.left, target);
}

在BST中插入一个元素，在BST删除一个元素

快速计算完全二叉树的节点

单调栈、单调队列的作用

双指针的使用技巧

快慢指针：判断是否有环、环的起始位置、链表的中心点、链表的倒数第k的元素、去除有序数组的重复元素
左右指针：二分查找、翻转数组、
滑动窗口

位运算相关

前缀和
字符串乘法
贪心：跳跃游戏
k个一组翻转链表
深度优先
1、全排列问题
2、一个环由个圈组成，把自然数1，2，…，N分别放在每一个圆内，数字的在两个相邻圈之和应该是一个素数。注意：第一圈数应始终为1。
3、油田问题
4、棋盘问题

二叉树的前中后序遍历

二叉树的广度优先搜索 （从上到下打印二叉树）

二叉树的深度优先搜索

树的子结构 （判断B是不是A的子结构。）

二叉树的镜像

对称二叉树

从上到下打印二叉树 同一层的节点按从左到右的顺序打印

从上到下打印二叉树 之字形顺序打印二叉树

二叉搜索树的后序

二叉树中和为某一值的路径

二叉搜索树与双向链表

序列化二叉树 层序遍历 BFS

二叉搜索树的第k大节点

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

二叉树的深度（后序遍历）

二叉树的最小深度

平衡二叉树

二叉搜索树的最近公共祖先

二叉树的最大宽度

最小高度树

合法二叉搜索树

二叉树中最大路径和

合并二叉树

翻转二叉树

监控二叉树

验证二叉树

最大二叉树

验证二叉搜索树

单值二叉树

二叉树的直径

二叉树的坡度

恢复一棵 BST

求二叉树中叶子节点的个数

求二叉树第K层的节点个数

求二叉树中最远的两个节点的距离

二叉搜索树中的众数

还原一棵二叉树

二叉搜索树序列

二叉搜索树总结

在BST中插入一个元素，在BST删除一个元素

快速计算完全二叉树的节点

单调栈、单调队列的作用

双指针的使用技巧

位运算相关

二叉树的广度优先搜索（从上到下打印二叉树）

树的子结构（判断B是不是A的子结构。）

从上到下打印二叉树同一层的节点按从左到右的顺序打印

从上到下打印二叉树之字形顺序打印二叉树

序列化二叉树层序遍历 BFS