binary tree好题选编

530. Minimum Absolute Difference in BST

注意：binary search tree中序遍历即得递增数组

法一：递归暴力搜索

//递归 暴力搜索
List<Integer> nodes;
public int getMinimumDifference(TreeNode root) {
    this.nodes=new ArrayList<>();
    dfs(root);
    int min=Integer.MAX_VALUE;
    for (int i = 1; i < nodes.size(); i++) {
        int dif=Math.abs(nodes.get(i)-nodes.get(i-1));
        min=Math.min(min,dif);
    }
    return min;
}

void dfs(TreeNode root){
    if(root==null){
        return;
    }
    //左 根 右
    dfs(root.left);
    nodes.add(root.val);
    dfs(root.right);
}

法二：双指针优化

在中序遍历过程中，记录之前的最小值，与当前差值比较

//递归 双指针
int min;
TreeNode pre;
public int getMinimumDifference(TreeNode root) {
    this.min=Integer.MAX_VALUE;
    dfs(root);
    return this.min;
}

void dfs(TreeNode root){
    if(root==null){
        return;
    }
    dfs(root.left);
    if(pre!=null){
        min=Math.min(root.val-pre.val,min);
    }
    pre=root;
    dfs(root.right);
}

法三：双指针优化的非递归写法（统一风格）：

//非递归
public int getMinimumDifference(TreeNode root) {
    TreeNode pre=null;
    int min=Integer.MAX_VALUE;
    Deque<TreeNode> stack=new LinkedList<>();
    //出栈：左 根 右
    //进栈：右 根 左
    stack.push(root);
    while(!stack.isEmpty()){
        TreeNode node=stack.pop();
        if(node!=null){
            if(node.right!=null){
                stack.push(node.right);
            }
            stack.push(node);
            stack.push(null);
            if(node.left!=null){
                stack.push(node.left);
            }
        }else{
            TreeNode cur=stack.pop();
            if(pre!=null){
                min=Math.min(min,cur.val-pre.val);
            }
            pre=cur;
        }
    }
    return min;
}

501. Find Mode in Binary Search Tree

法一：笨方法，未利用BST特性

public class LeetCode501 {
    Map<Integer,Integer> map;
    public int[] findMode(TreeNode root) {
        this.map=new HashMap<>();
        inorder(root);
        int max=0;
        for (Integer i : map.keySet()) {
            max=Math.max(max,map.get(i));
        }
        List<Integer> list=new ArrayList<>();
        for (Integer i : map.keySet()) {
            if(map.get(i)==max){
                list.add(i);
            }
        }
        int[] res=new int[list.size()];
        for (int i = 0; i < res.length; i++) {
            res[i]=list.get(i);
        }
        return res;
    }

    void inorder(TreeNode root){
        //左 根 右
        if(root==null){
            return;
        }
        inorder(root.left);
        map.put(root.val,map.getOrDefault(root.val,0)+1);
        inorder(root.right);
    }
}

法二：利用BST的中序遍历特性，递归写法

List<Integer> list;
int maxCount;
int pre;
int curCount;
public int[] findMode(TreeNode root) {
    this.list=new LinkedList<>();
    this.maxCount=0;
    this.pre=Integer.MIN_VALUE;
    this.curCount=0;
    inorder(root);
    int[] res=new int[list.size()];
    for (int i = 0; i < res.length; i++) {
        res[i]=list.get(i);
    }
    return res;
}

void inorder(TreeNode root){
    if(root==null){
        return;
    }
    inorder(root.left);
    if(pre!=root.val || pre==Integer.MIN_VALUE){
        curCount=1;
    }else{
        curCount++;
    }
    if(curCount>maxCount){
        maxCount=curCount;
        list.removeAll(list);
        list.add(root.val);
    }else if(curCount==maxCount){
        list.add(root.val);
    }
    pre=root.val;
    inorder(root.right);
}

法二：利用BST的中序遍历特性，统一风格非递归写法

public int[] findMode(TreeNode root) {
    List<Integer> list=new LinkedList<>();
    int maxCount=0;
    int curCount=0;
    int pre=Integer.MIN_VALUE;
    Deque<TreeNode> stack=new LinkedList<>();
    stack.push(root);
    while(!stack.isEmpty()){
        TreeNode node=stack.pop();
        if(node!=null){ //只负责访问
            //出栈 左 根 右
            //进栈 右 根 左
            if(node.right!=null){
                stack.push(node.right);
            }
            stack.push(node);
            stack.push(null);
            if(node.left!=null){
                stack.push(node.left);
            }
        }else{ //只负责处理
            node=stack.pop();
            if(pre==Integer.MIN_VALUE || pre!=node.val){
                curCount=1;
            }else{
                curCount++;
            }
            if(curCount>maxCount){
                maxCount=curCount;
                list.removeAll(list);
                list.add(node.val);
            }else if(curCount==maxCount){
                list.add(node.val);
            }
            pre=node.val;
        }
    }
    int[] res=new int[list.size()];
    for (int i = 0; i < res.length; i++) {
        res[i]=list.get(i);
    }
    return res;
}

222. Count Complete Tree Nodes

利用完全二叉树的特点：完全二叉树的左右子树中至少有一棵是满二叉树，另一棵为完全二叉树：

若左右子树高度相同，则左子树必为满二叉树
若左右子树高度不同，则右子树必为满二叉树

那么满二叉树和根节点的总个数为2^n，其中n为满二叉树的深度

public class LeetCode222 {
    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        int leftDepth=depth(root.left);
        int rightDepth=depth(root.right);
        if(leftDepth==rightDepth){
            return (1<<leftDepth)+countNodes(root.right); //括号不能省略，<<优先级低于+
        }else{
            return (1<<rightDepth)+countNodes(root.left);
        }
    }

    int depth(TreeNode root){
        /*if(root==null){
            return 0;
        }else{
            return 1+Math.max(depth(root.left),depth(root.right));
        }*/
        int depth=0;
        while(root!=null){
            root=root.left;
            depth++;
        }
        return depth;
    }
}

701. Insert into a Binary Search Tree

public class LeetCode701 {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root==null){
            TreeNode node=new TreeNode(val);
            return node;
        }
        if(root.val<val){
            root.right=insertIntoBST(root.right,val);
        }else{
            root.left=insertIntoBST(root.left,val);
        }
        return root;
    }
}

450. Delete Node in a BST

当找到待删除node时，分三类讨论：

若为叶子节点，则直接删除，返回null即可
若左子树或右子树为空，则直接删除，返回右子树或左子树即可
若左右子树都非空，则找到右子树中的最小节点min；从右子树中删除min；调换root与min，使min成为新的root并返回

public class LeetCode450 {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null){
            return null;
        }
        if(root.val==key){
            if(root.left==null && root.right==null){
                return null;
            }
            if(root.left==null){
                return root.right;
            }
            if(root.right==null){
                return root.left;
            }
            TreeNode node=findMin(root.right);
            root.right=deleteNode(root.right,node.val);
            node.left=root.left;
            node.right=root.right;
            root=node;
        }else if(root.val<key){
            root.right=deleteNode(root.right,key);
        }else{
            root.left=deleteNode(root.left,key);
        }
        return root;
    }

    TreeNode findMin(TreeNode root){
        while(root.left!=null){
            root=root.left;
        }
        return root;
    }
}

669. Trim a Binary Search Tree

public class LeetCode669 {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        //trim:root.val<low时，删除root和root.left
        //trim:root.val>high时，删除root和root.right
        if(root==null){
            return null;
        }
        if(root.val>=low && root.val<=high){
            root.left=trimBST(root.left,low,high);
            root.right=trimBST(root.right,low,high);
        }else if(root.val<low){
            root=trimBST(root.right,low,high);
        }else if(root.val>high){
            root=trimBST(root.left,low,high);
        }
        return root;
    }
}

108. Convert Sorted Array to Binary Search Tree

法一：递归

public class LeetCode108 {
    public TreeNode sortedArrayToBST(int[] nums) {
        //find mid
        return helper(nums,0,nums.length-1);
    }

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

法二：迭代(难想!)

迭代法可以通过三个队列来模拟，一个队列放遍历的节点，一个队列放左区间下标，一个队列放右区间下标。

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.size() == 0) return nullptr;

        TreeNode* root = new TreeNode(0);   // 初始根节点
        queue<TreeNode*> nodeQue;           // 放遍历的节点
        queue<int> leftQue;                 // 保存左区间下标
        queue<int> rightQue;                // 保存右区间下标
        nodeQue.push(root);                 // 根节点入队列
        leftQue.push(0);                    // 0为左区间下标初始位置
        rightQue.push(nums.size() - 1);     // nums.size() - 1为右区间下标初始位置

        while (!nodeQue.empty()) {
            TreeNode* curNode = nodeQue.front();
            nodeQue.pop();
            int left = leftQue.front(); leftQue.pop();
            int right = rightQue.front(); rightQue.pop();
            int mid = left + ((right - left) / 2);

            curNode->val = nums[mid];       // 将mid对应的元素给中间节点

            if (left <= mid - 1) {          // 处理左区间
                curNode->left = new TreeNode(0);
                nodeQue.push(curNode->left);
                leftQue.push(left);
                rightQue.push(mid - 1);
            }

            if (right >= mid + 1) {         // 处理右区间
                curNode->right = new TreeNode(0);
                nodeQue.push(curNode->right);
                leftQue.push(mid + 1);
                rightQue.push(right);
            }
        }
        return root;
    }
};

538. Convert BST to Greater Tree

法一：递归

public class LeetCode538 {
    int sum;
    public TreeNode convertBST(TreeNode root) {
        sum=0;
        dfs(root);
        return root;
    }

    void dfs(TreeNode root){
        //left root right
        //right root left
        if(root==null){
            return;
        }
        dfs(root.right);
        sum+=root.val;
        root.val=sum;
        dfs(root.left);
    }
}

法二：迭代

public TreeNode convertBST(TreeNode root) {
    if(root==null){
        return null;
    }
    Deque<TreeNode> stack=new LinkedList<>();
    stack.push(root);
    int sum=0;
    while(!stack.isEmpty()){
        TreeNode node=stack.pop();
        if(node!=null){
            //left root right   inorder出栈顺序	ASC
            //right root left	reverse_inorder出栈顺序	DESC
            //left root right	reverse_inorder进栈顺序	
            if(node.left!=null){
                stack.push(node.left);
            }
            stack.push(node);
            stack.push(null);
            if(node.right!=null){
                stack.push(node.right);
            }
        }else{
            node=stack.pop();
            sum+=node.val;
            node.val=sum;
        }
    }
    return root;
}

114. Flatten Binary Tree to Linked List

public class LeetCode114 {

    TreeNode pre;
    
    public void flatten(TreeNode root) {
        dfs(root);
    }

    void dfs(TreeNode cur){
        if(cur==null){
            return;
        }
        TreeNode right=cur.right;
        if(pre!=null){
            pre.left=null;
            pre.right=cur;
        }
        pre=cur;
        dfs(cur.left);
        dfs(right);
    }
}

96. Unique Binary Search Trees

思路：

一棵BST由root,left和right构成

其中left和right也是BST
n个节点的BST共有一下几种可能：

left right

n-1 0

n-2 1

n-3 2

… …

1 n-2

0 n-1

left	right
n-1	0
n-2	1
n-3	2
…	…
1	n-2
0	n-1

public class LeetCode96 {
    public int numTrees(int n) {
        int[] dp=new int[n+1];
        dp[0]=1;
        dp[1]=1;
        for (int i = 2; i <= n; i++) {
            for (int j = i-1; j >= 0; j--) {
                dp[i]+=dp[j]*dp[i-1-j];
            }
        }
        return dp[n];
    }
}

95. Unique Binary Search Trees II

思路：

穷举root
穷举left
穷举right
构造树

public class LeetCode95 {
    public List<TreeNode> generateTrees(int n) {
        return build(1,n);
    }

    List<TreeNode> build(int low, int high){
        List<TreeNode> res=new ArrayList<>();
        if(low>high){
            res.add(null);
            return res;
        }
        for(int i=low; i<=high; i++){
            List<TreeNode> left=build(low,i-1);
            List<TreeNode> right=build(i+1,high);
            for (TreeNode leftNode : left) {
                for (TreeNode rightNode : right) {
                    TreeNode root=new TreeNode(i);
                    root.left=leftNode;
                    root.right=rightNode;
                    res.add(root);
                }
            }
        }
        return res;
    }
}

101. Symmetric Tree

法一：递归

public class LeetCode101 {
    public boolean isSymmetric(TreeNode root) {
        return helper(root.left,root.right);
    }

    boolean helper(TreeNode left, TreeNode right){
        if(left==null && right==null){
            return true;
        }
        if(left==null || right==null || left.val!=right.val){
            return false;
        }
        return helper(left.left,right.right) && helper(left.right,right.left);
    }
}

法二：迭代

注意：

不能直接由中序遍历结果或层序遍历结果判断
可以参考层序遍历，只是null也进队
每次判断头尾是否相等，直到队为空
更新队列时，分别在头和尾插入

public boolean isSymmetric(TreeNode root) {
    Deque<TreeNode> deque=new LinkedList<>();
    deque.push(root.left);
    deque.push(root.right);
    while(!deque.isEmpty()){
        TreeNode left=deque.pollFirst();
        TreeNode right=deque.pollLast();
        if(left==null && right==null){
            continue;
        }
        if(left==null || right==null || left.val!=right.val){
            return false;
        }
        deque.offerFirst(left.right);
        deque.offerFirst(left.left);
        deque.offerLast(right.left);
        deque.offerLast(right.right);
    }
    return true;
}

297. Serialize and Deserialize Binary Tree

tree to string
string to tree

DFS: correct but slow

public String rserialize(TreeNode root, String str) {
  // Recursive serialization.
  if (root == null) {
    str += "null,";
  } else {
    str += str.valueOf(root.val) + ",";
    str = rserialize(root.left, str);
    str = rserialize(root.right, str);
  }
  return str;
}

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
  return rserialize(root, "");
}
  
    public TreeNode rdeserialize(List<String> l) {
  // Recursive deserialization.
  if (l.get(0).equals("null")) {
    l.remove(0);
    return null;
  }

  TreeNode root = new TreeNode(Integer.valueOf(l.get(0)));
  l.remove(0);
  root.left = rdeserialize(l);
  root.right = rdeserialize(l);

  return root;
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
  String[] data_array = data.split(",");
  List<String> data_list = new LinkedList<String>(Arrays.asList(data_array));
  return rdeserialize(data_list);
}

DFS: wrong answer

注意：val可以重复，无法通过preOrder中root的值定位其在inOrder中的位置！！！！！！！！！！！！！！！！！！！！！！！

StringBuilder sb;
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
    if(root==null){
        return "";
    }
    sb=new StringBuilder();
    pre(root);
    sb.deleteCharAt(sb.length()-1);
    sb.append("#");
    in(root);
    sb.deleteCharAt(sb.length()-1);
    return sb.toString();
}

// Decodes your encoded data to tree.
// 1,2,3,4,5
// 2,1,4,3,5
// 1, 2, 3 4 5
// 2, 1, 4 3 5

//exception: 
//3 2 3 4
//3 2 3 4
public TreeNode deserialize(String data) {
    if(data==""){
        return null;
    }
    String[] split = data.split("#");
    String[] pre=split[0].split(",");
    String[] in=split[1].split(",");
    int n=pre.length;
    return build(pre,in,0,n-1,0,n-1);
}

TreeNode build(String[] pre, String[] in, int pLeft, int pRight, int iLeft, int iRight){
    if(pLeft>pRight || iLeft>iRight){
        return null;
    }
    String s=pre[pLeft];
    int val=Integer.valueOf(s);
    TreeNode root=new TreeNode(val);
    int i=iLeft;
    for(; i<=iRight; i++){
        if(in[i].equals(s)){
            break;
        }
    }
    root.left=build(pre,in,pLeft+1,pLeft+i-iLeft,iLeft,i-1);
    root.right=build(pre,in,pLeft+i-iLeft+1,pRight,i+1,iRight);
    return root;
    //[iLeft,i-1]
    //[i+1,iRight]
    //[pLeft+1,pLeft+1+i-1-iLeft]=> [pLeft+1,pLeft+i-iLeft]
    //[pLeft+i-iLeft+1,pRight]
}

void pre(TreeNode cur){
    if(cur==null){
        return;
    }
    sb.append(cur.val);
    sb.append(",");
    pre(cur.left);
    pre(cur.right);
}

void in(TreeNode cur){
    if(cur==null){
        return;
    }
    in(cur.left);
    sb.append(cur.val);
    sb.append(",");
    in(cur.right);
}

BFS:

// Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "";
        String n = "null", sep = ",";
        Queue<TreeNode> dq = new LinkedList<>();
        dq.offer(root);
        int size = 0;
        TreeNode cur;
        StringBuilder sb = new StringBuilder();
        
        while (!dq.isEmpty()) {
            size = dq.size();
            for (int i = 0; i < size; ++i) {
                cur = dq.poll();
                if (cur != null) {
                    sb.append(cur.val);
                    dq.offer(cur.left);
                    dq.offer(cur.right);
                } else {
                    sb.append(n);
                }
                sb.append(sep);
            }
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) return null;
        String[] vals = data.split(",");
        if (vals == null || vals.length == 0) return null;
        
        String n = "null";
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        TreeNode cur, next;
        Deque<TreeNode> dq = new ArrayDeque<>();
        int size = 0, index = 1;
        dq.offer(root);
        
        while (!dq.isEmpty()) {
            size = dq.size();
            for (int i = 0; i < size; ++i) {
                cur = dq.poll();
                
                for (int j = index; j < index + 2 && j < vals.length; ++j) {
                    if (vals[j].equals(n)) {
                        if (j % 2 == 1) {
                            cur.left = null;
                        } else {
                            cur.right = null;
                        }
                    } else {
                        next = new TreeNode(Integer.parseInt(vals[j]));
                        dq.offer(next);
                        if (j % 2 == 1) {
                            cur.left = next;
                        } else {
                            cur.right = next;
                        }
                    }
                }
                
                index += 2;
            }
        }
        
        return root;
    }

314. Binary Tree Vertical Order Traversal

class Node{
      int index;
      TreeNode node;
      Node(TreeNode node, int index){
          this.index=index;
          this.node=node;
      }
}

public List<List<Integer>> verticalOrder(TreeNode root) {
    List<List<Integer>> res=new ArrayList<>();
      if(root==null){
          return res;
      }
    TreeMap<Integer,List<Integer>> map=new TreeMap<>();
    Deque<Node> q=new LinkedList<>();
    q.offer(new Node(root,0));
    while(!q.isEmpty()){
        Node node=q.poll();
        int index=node.index;
        TreeNode treeNode=node.node;
        map.putIfAbsent(index,new ArrayList<>());
        map.get(index).add(treeNode.val);
        if(treeNode.left!=null){
            q.offer(new Node(treeNode.left,index-1));
        }
        if(treeNode.right!=null){
            q.offer(new Node(treeNode.right,index+1));
        }
    }
    for (List<Integer> list : map.values()) {
        res.add(list);
    }
    return res;
}

331. Verify Preorder Serialization of a Binary Tree

Some used stack. Some used the depth of a stack. Here I use a different perspective. In a binary tree, if we consider null as leaves, then

all non-null node provides 2 outdegree and 1 indegree (2 children and 1 parent), except root
all null node provides 0 outdegree and 1 indegree (0 child and 1 parent).

Suppose we try to build this tree. During building, we record the difference between out degree and in degree diff = outdegree - indegree. When the next node comes, we then decrease diff by 1, because the node provides an in degree. If the node is not null, we increase diff by 2, because it provides two out degrees. If a serialization is correct, diff should never be negative and diff will be zero when finished.

public boolean isValidSerialization(String preorder) {
    String[] nodes = preorder.split(",");
    int diff = 1;
    for (String node: nodes) {
        if (--diff < 0) return false;
        if (!node.equals("#")) diff += 2;
    }
    return diff == 0;
}

951. Flip Equivalent Binary Trees

public boolean flipEquiv(TreeNode root1, TreeNode root2) {
    if(root1==null && root2==null){
        return true;
    }
    if(root1==null || root2==null || root1.val!=root2.val){
        return false;
    }
    return flipEquiv(root1.left,root2.left) && flipEquiv(root1.right,root2.right)
            || flipEquiv(root1.left,root2.right) && flipEquiv(root1.right,root2.left);
}

814. Binary Tree Pruning

public TreeNode pruneTree(TreeNode root) {
    if(root==null){
        return null;
    }
    TreeNode l=pruneTree(root.left);
    TreeNode r=pruneTree(root.right);
    if(l==null && r==null && root.val==0){
        return null;
    }
    root.left=l;
    root.right=r;
    return root;
}

958. Check Completeness of a Binary Tree

public boolean isCompleteTree(TreeNode root) {
    Deque<TreeNode> q=new LinkedList<>();
    q.offer(root);
    boolean lastLevel=false;
    while(q.isEmpty()){
        int size=q.size();
        while(size-->0){
            TreeNode cur=q.poll();
            if(cur!=null){
                if(lastLevel){
                    return false;
                }
                q.offer(cur.left);
                q.offer(cur.right);
            }else{
                lastLevel=true;
            }
        }
    }
    return true;
}

1110. Delete Nodes And Return Forest

List<TreeNode> res=new ArrayList<>();
Set<Integer> set=new HashSet<>();
public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
    for (int i : to_delete) {
        set.add(i);
    }
    dfs(root);
    if(root.val!=0){
        res.add(root);
    }
    return res;
}

void dfs(TreeNode node){
    if(node==null){
        return;
    }
    dfs(node.left);
    dfs(node.right);
    if(node.left!=null && node.left.val==0){
        node.left=null;
    }
    if(node.right!=null && node.right.val==0){
        node.right=null;
    }
    if(set.contains(node.val)){
        if(node.left!=null){
            res.add(node.left);
        }
        if(node.right!=null){
            res.add(node.right);
        }
        node.val=0; //to be deleted by its parent
    }
}

654. Maximum Binary Tree

This is also called a Cartesian Tree. One interesting property is that if we do an in-order traversal, we get the array back which we used to create it.

int[] arr;
public TreeNode constructMaximumBinaryTree(int[] nums) {
    arr=nums;
    return dfs(0,arr.length-1);
}

TreeNode dfs(int left, int right){
    if(left>right){
        return null;
    }
    if(left==right){
        return new TreeNode(arr[left]);
    }
    int max=0;
    int idx=0;
    for(int i=left; i<=right; i++){
        if(arr[i]>max){
            max=arr[i];
            idx=i;
        }
    }
    TreeNode node=new TreeNode(arr[idx]);
    node.left=dfs(left,idx-1);
    node.right=dfs(idx+1,right);
    return node;
}

255. Verify Preorder Sequence in Binary Search Tree

public boolean verifyPreorder(int[] preorder) {
    Deque<Integer> stack=new LinkedList<>();
    int low=Integer.MIN_VALUE;
    for (int p : preorder) {
        if(p<low){
            return false;
        }
        while(!stack.isEmpty() && p>stack.peek()){
            low=stack.pop();
        }
        stack.push(p);
    }
    return true;
}

510. Inorder Successor in BST II

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

public Node inorderSuccessor(Node node) {

    //down right
    if(node.right!=null){
        Node r=node.right;
        while(r.left!=null){
            r=r.left;
        }
        return r;
    }
    //up right
    Node p=node.parent;
    while(p!=null && p.val<node.val){
        p=p.parent;
    }
    return p;
}

1120. Maximum Average Subtree

double max=0;
public double maximumAverageSubtree(TreeNode root) {
    dfs(root);
    return max;
}

int[] dfs(TreeNode node){
      if(node==null){
          return null;
      }
      int sum=node.val;
      int count=1;
      int[] l=dfs(node.left);
      int[] r=dfs(node.right);
      if(l!=null){
          sum+=l[0];
          count+=l[1];
      }
    if(r!=null){
        sum+=r[0];
        count+=r[1];
    }
    max=Math.max(max,(double)sum/count);
    return new int[]{sum,count};
}

1361. Validate Binary Tree Nodes

反思：

没有现成的树，先建树
想要建树，先找root

public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
    int root=findRoot(n,leftChild,rightChild);
    if(root==-1){
        return false;
    }
    //bfs to traverse from root and detect cycle
    boolean[] visited=new boolean[n];
    Deque<Integer> q=new LinkedList<>();
    q.offer(root);
    int size=0;
    while(!q.isEmpty()){
        int cur=q.poll();
        visited[cur]=true;
        size++;
        if(leftChild[cur]!=-1){
            if(visited[leftChild[cur]]){
                return false;
            }
            q.offer(leftChild[cur]);
        }
        if(rightChild[cur]!=-1){
            if(visited[rightChild[cur]]){
                return false;
            }
            q.offer(rightChild[cur]);
        }
    }
    return size==n;
}

private int findRoot(int n, int[] left, int[] right){
    boolean[] isChild=new boolean[n];
    for (int i : left) {
        if(i!=-1){
            isChild[i]=true;
        }
    }
    for (int i : right) {
        if(i!=-1){
            isChild[i]=true;
        }
    }
    for (int i = 0; i < n; i++) {
        if(!isChild[i]){
            return i;
        }
    }
    return -1;
}

25. Reverse Nodes in k-Group

public ListNode reverseKGroup(ListNode head, int k) {
            //recursion, LinkedList
    ListNode curr=head;
    int count=0;
    while(curr!=null && count!=k){
        //find the k+1 node
        curr=curr.next;
        count++;
    }
    if(count==k){
        curr=reverseKGroup(curr,k);
        
        while(count-->0){
            ListNode temp=head.next;
            head.next=curr;
            curr=head;
            head=temp;
        }
        head=curr;
    }
    return head; //we run out of nodes before we hit count ==k 
}

binary tree好题选编

法一：递归 暴力搜索

法二：双指针优化

法三：双指针优化的非递归写法（统一风格）：

法一：笨方法，未利用BST特性

法二：利用BST的中序遍历特性，递归写法

法二：利用BST的中序遍历特性，统一风格非递归写法

法一：递归

法二：迭代(难想!)

法一：递归

法二：迭代

297. Serialize and Deserialize Binary Tree

DFS: correct but slow

DFS: wrong answer

BFS:

314. Binary Tree Vertical Order Traversal

331. Verify Preorder Serialization of a Binary Tree

951. Flip Equivalent Binary Trees

814. Binary Tree Pruning

958. Check Completeness of a Binary Tree

1110. Delete Nodes And Return Forest

654. Maximum Binary Tree

255. Verify Preorder Sequence in Binary Search Tree

510. Inorder Successor in BST II

1120. Maximum Average Subtree

1361. Validate Binary Tree Nodes

25. Reverse Nodes in k-Group

法一：递归暴力搜索