刷题记录｜目标101题--树

写在前面

开个贴记录一下 刷题的过程，目前参照 leetcode101，目标101题，由于太久没写java了，也会涉及到一些java的基础用法，希望能和大家共勉吧～

已刷链接：

树的结构

树的递归

No.1 Maximum Depth of Binary Tree

题目：https://leetcode.com/problems/maximum-depth-of-binary-tree/

解题思路：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        return root == null ? 0 : (1 + Math.max(maxDepth(root.left),maxDepth(root.right)));
    }
}

No.2 Balanced Binary Tree

题目：https://leetcode.com/problems/balanced-binary-tree/

解题思路：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        return helper(root) != -1;
    }
    private int helper(TreeNode root) {
        if (root == null) return 0;
        int left = helper(root.left);
        int right = helper(root.right);
        if (left == - 1 || right == -1 || Math.abs(left - right) > 1) {
            return -1;
        }
        return Math.max(left,right) + 1;
    }
}

No.3 Diameter of Binary Tree

题目：https://leetcode.com/problems/diameter-of-binary-tree/

解题思路：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int res = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        helper(root);
        return res;
    }
    private int helper(TreeNode root) {
        if (root == null) return 0;
        int left = helper(root.left);
        int right = helper(root.right);
        res = Math.max(res,left+right);
        return 1 + Math.max(left,right);
    }
}

No.4 Path Sum III

题目：https://leetcode.com/problems/path-sum-iii/

解题思路：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        return root == null ? 0 : (int)(pathSumWithRoot(root,targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum));
    }
    private long pathSumWithRoot(TreeNode root, long targetSum) {
        if (root == null) return 0;
        long count = 0;
        if (root.val == targetSum) {
            count = 1;
        }
        count += pathSumWithRoot(root.left,targetSum - root.val);
        count += pathSumWithRoot(root.right,targetSum - root.val);
        return count;
    }
}

No.5 Symmetric Tree

题目：https://leetcode.com/problems/symmetric-tree/

解题思路：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return root == null ? true : isSymmetric(root.left,root.right);
    }
    private boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        return isSymmetric(left.left,right.right) && isSymmetric(left.right,right.left);
    }
}

No.6 Delete Nodes And Return Forest

题目：https://leetcode.com/problems/delete-nodes-and-return-forest/

解题思路：

递归先处理后续的子节点，拿到后续的节点的root时假定他们已经处理好了应该删除的元素，然后再去判断这个元素是否要被删除

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<TreeNode> tree = new ArrayList<TreeNode>();
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        Set<Integer> to_delete_set = new HashSet<Integer>();
        for (int i : to_delete) {
            to_delete_set.add(i);
        }
        root = helper(root,to_delete_set);
        if (root != null) {
            tree.add(root);
        }
        return tree;
    }
    private TreeNode helper(TreeNode root, Set<Integer> dic) {
        if (root == null) {
            return null;
        }
        root.left = helper(root.left, dic);
        root.right = helper(root.right, dic);
        if (dic.contains(root.val)) {
            if (root.left != null) {
                tree.add(root.left);
            }
            if (root.right != null) {
                tree.add(root.right);
            }
            root = null;
        }
        return root;
    }
}

No.7 Invert Binary Tree

题目链接：https://leetcode.com/problems/invert-binary-tree/

解题思路：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode temp = invertTree(root.right);
        root.right = invertTree(root.left);
        root.left = temp;
        return root;
    }
}

No.8 Merge Two Binary Trees

题目链接：https://leetcode.com/problems/merge-two-binary-trees/submissions/

解题思路：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return null;
        if (root1 == null || root2 == null) return root1 == null ? root2 : root1;
        root1.val = root1.val + root2.val;
        root1.left = mergeTrees(root1.left,root2.left);
        root1.right = mergeTrees(root1.right,root2.right);
        return root1;
    }
}

No.9 Subtree of Another Tree

题目：https://leetcode.com/problems/subtree-of-another-tree/submissions/

解题思路：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) return false;
        if (isSub(root,subRoot)) return true;
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    } 
    public boolean isSub(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) return true;
        if (root == null || subRoot == null) return false;
        if (root.val == subRoot.val) {
            return isSub(root.left, subRoot.left) && isSub(root.right, subRoot.right);
        } else {
            return false;
        }
    }
}

No.10 Sum of Left Leaves

题目链接：https://leetcode.com/problems/sum-of-left-leaves/

解题思路：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root.left == null && root.right == null) return 0;
        return helper(root.left, true) + helper(root.right, false);
    }
    public int helper(TreeNode root, boolean isLeft) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return isLeft ? root.val : 0;
        return helper(root.left, true) + helper(root.right, false);
    }
}

树的层次遍历

No.1 Average of Levels in Binary Tree

题目链接：https://leetcode.com/problems/average-of-levels-in-binary-tree/

思路：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        List<Double> res = new LinkedList<Double>();
        que.add(root);
        while(que.size() != 0) {
            int size = que.size();
            long sum = 0;
            for(int i = 0; i < size; i ++) {
                TreeNode cur = que.poll();
                sum += cur.val;
                if (cur.left != null) {
                    que.offer(cur.left);
                }
                if (cur.right != null) {
                    que.offer(cur.right);
                }
            }
            res.add((sum * 1.0) / (size * 1.0));
        }
        return res;
    }
}

No.2 Find Bottom Left Tree Value

题目链接：https://leetcode.com/problems/find-bottom-left-tree-value/submissions/

解题思路：

queque先入后出

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        if (root.left == null && root.right == null) return root.val;
        Queue<TreeNode> que = new LinkedList<TreeNode> ();
        que.offer(root);
        TreeNode temp = null;
        while(que.size() != 0) {
            int size = que.size();
            temp = que.peek();
            for (int i = 0; i < size; i++) {
                TreeNode cur = que.poll();
                if (cur.left != null) que.offer(cur.left);
                if (cur.right != null) que.offer(cur.right);
            }
        }
        return temp == null ? 0 : temp.val;
    }
}

树的前中后序遍历

前序遍历是父节点-》左子节点-〉右子节点

中序遍历是左子节点-》父节点-〉右子节点

后序遍历是左子节点-》右子节点-〉父节点

No. 1 Construct Binary Tree from Preorder and Inorder Traversal

题目：https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

解题思路：

前序遍历的第一个节点是树的根节点，在中序遍历中根节点左边的是左子树，右边是右子树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = preorder.length;
        return helper(preorder,0,len - 1,inorder,0,len - 1,len);
    }
    private TreeNode helper(int[] preorder,int pl,int pr, int[] inorder, int il,int ir,int n) {
        if (pl >= n || il >= n || pl < 0 || il < 0 || pl > pr || il > ir) return null;
        TreeNode root = new TreeNode(preorder[pl]);
        int len = pr - pl + 1;
        if (len == 1) return root;
        int i = 0;
        for (; i < len; i++) {
            if (inorder[i + il] == preorder[pl]) {
                break;
            }
        }
        root.left = helper(preorder,1+pl,i+pl,inorder,il,i - 1+il,n);
        root.right = helper(preorder,i+1+pl,len - 1+pl,inorder,i+1+il,len - 1+il,n);
        return root;
    }
}

No.2 Binary Tree Preorder Traversal

题目：https://leetcode.com/problems/binary-tree-preorder-traversal/

解题思路：

递归：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> res = new ArrayList<Integer>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) return res;
        res.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return res;
    }
}

非递归：

递归的本质是栈的调用，可以用栈来实现。注意栈是先入后出，要先把right塞入栈才是前序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) return res;
        Stack<TreeNode> sta = new Stack<TreeNode>();
        sta.push(root);
        while (!sta.empty()) {
            TreeNode cur = sta.pop();
            res.add(cur.val);
            if (cur.right != null) {
                sta.push(cur.right);
            }
            if (cur.left != null) {
                sta.push(cur.left);
            }
        }
        return res;
    }
}

No.3 Construct Binary Tree from Preorder and Postorder Traversal

题目：https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/

题目解析：

前序的第一个节点是根节点，则他的子树的第一个节点也是根节点，后续的最后一个节点是根节点，通过根节点可以将树分割

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        return helper(preorder,0,preorder.length - 1,postorder, 0, postorder.length - 1);
    }
    private TreeNode helper(int[] preorder,int preS, int preE,int[] postorder, int postS, int postE) {
        if (preE >= preorder.length || postE >= preorder.length || preS > preE || postS > postE) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preS]);
        if (preS == preE) {
            return root;
        }
        int leftPreRoot = preS + 1;
        int leftPostRoot = postS;
        for (; leftPostRoot <= postE; leftPostRoot++) {
            if (postorder[leftPostRoot] == preorder[leftPreRoot]) {
                break;
            }
        }
        int leftPreEnd = leftPostRoot - postS + leftPreRoot;
        root.left = helper(preorder,leftPreRoot, leftPreEnd,
                          postorder,postS,leftPostRoot);
        root.right = helper(preorder,leftPreEnd+1,preE,
                           postorder,leftPostRoot + 1,postE -1);
        return root;
    }
}

No.4 Construct Binary Tree from Inorder and Postorder Traversal

题目：https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

解题思路：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return helper(inorder,0,inorder.length - 1,postorder,0,postorder.length - 1);
    }
    private TreeNode helper(int[] inorder,int inS,int inE, int[] postorder, int postS,int postE) {
        if (inE > inorder.length - 1 || postE > postorder.length - 1 || inS > inE || postS > postE) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postE]);
        if (inS == inE) return root;
        int inRoot = inS;
        for (;inRoot <= inE; inRoot++) {
            if (inorder[inRoot] == postorder[postE]) {
                break;
            }
        }
        int postLeftE = postS + inRoot - 1 - inS;
        root.left = helper(inorder,inS,inRoot - 1,
                          postorder,postS,postLeftE);
        root.right = helper(inorder,inRoot+1,inE,
                           postorder,postLeftE+1,postE - 1);
        return root;
    }
}

No.5 Binary Tree Inorder Traversal

题目：https://leetcode.com/problems/binary-tree-inorder-traversal/

解题思路：

/**
 * Definition for a binary tree node.
 * public class reeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> res = new LinkedList<Integer>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null) return null;
        Stack<TreeNode> s = new Stack<TreeNode>();
        s.push(root);
        while(s.size() != 0) {
            TreeNode cur = s.peek();
            while(cur.left != null) {
                s.push(cur.left);
                cur = cur.left;
            }
            res.add(cur.val);
            s.pop();
            if (cur.right != null) s.push(cur.right);
        }
        return res;
    }
}

No. 6 Binary Tree Postorder Traversal

题目：https://leetcode.com/problems/binary-tree-postorder-traversal/

题目解析：

这里利用了 java 的 linkedlist 有 addFirst() 方法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    LinkedList<Integer> res = new LinkedList<Integer> ();
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) return res;
        Stack<TreeNode> sta = new Stack<TreeNode>();
        sta.push(root);
        while(!sta.isEmpty()) {
            TreeNode cur = sta.pop();
            res.addFirst(cur.val);
            if (cur.left != null) {
                sta.push(cur.left);
            }
            if (cur.right != null) {
                sta.push(cur.right);
            }
        }
        return res;
    }
}

二叉查找树

No.1 Recover Binary Search Tree

题目：https://leetcode.com/problems/recover-binary-search-tree/

解题思路：

因为二叉查找树是一个中序遍历可以为排好序的数组，所以我们可以中序遍历，去寻找不符合顺序的值。

这里需要注意，如果遍历一次只遇到了一次异常，说明是那两个相邻元素的值翻了，交换这两个；

但是如果遍历一次遇到了两次异常，则是这两个值相反，需要交换这两个值，注意这里是交换第一次异常的前一个值和第二次异常的后一个值。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    TreeNode pre, mis1, mis2;
    public void recoverTree(TreeNode root) {
        inorder(root);
        if (mis2 != null && mis1 != null) {
            int temp = mis2.val;
            mis2.val = mis1.val;
            mis1.val = temp;
        }
        return;
    }
    private void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        if (pre != null && pre.val > root.val) {
            mis1 = mis2 == null ? pre : mis1;
            mis2 = root;
        }
        pre = root;
        inorder(root.right);
    }
}

No.2 Trim a Binary Search Tree

题目链接：https://leetcode.com/problems/trim-a-binary-search-tree/

解题思路：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) return null;
        if (root.val < low) {
            return trimBST(root.right, low, high);
        } else if (root.val > high) {
            return trimBST(root.left, low, high);
        } else if (root.val == low) {
            root.right = trimBST(root.right,low, high);
            root.left = null;
        } else if (root.val == high) {
            root.left = trimBST(root.left,low, high);
            root.right = null;
        } else {
            root.left = trimBST(root.left,low,high);
            root.right = trimBST(root.right,low, high);
        }
        return root;
    }
}

No.3 Convert BST to Greater Tree

题目链接：https://leetcode.com/problems/convert-bst-to-greater-tree/

解题思路：

利用bst的中序遍历是递增数组的特性，逆者中序遍历遍历一遍即可

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode convertBST(TreeNode root) {
        if (root == null) return null;
        if (root.left == null && root.right == null) return root;
        helper(root,0);
        return root;
    }
    public int helper(TreeNode root,int plus) {
        if (root == null) return 0;
        if (root.right != null) {
            root.val += helper(root.right,plus);
        } else {
            root.val += plus;
        }
        if (root.left != null) {
            return helper(root.left,root.val);
        } else {
            return root.val;
        }
    }
}

No.4 Lowest Common Ancestor of a Binary Search Tree

题目链接：https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

解题思路：

利用bst的特性进行查找

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (root.val == p.val || root.val == q.val) return root.val == p.val ? p : q;
        if ((root.val > p.val && root.val < q.val) || (root.val < p.val && root.val > q.val)) {
            return root;
        } else if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left,p,q);
        } else if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right,p,q);
        }
        return null;
    }
}

No.5 Minimum Absolute Difference in BST

题目：https://leetcode.com/problems/minimum-absolute-difference-in-bst/

解题思路：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int min = Integer.MAX_VALUE;
    int pre = -1;
    public int getMinimumDifference(TreeNode root) {
        if (root == null) return Integer.MAX_VALUE;
        getMinimumDifference(root.left);
        if (pre != -1) {
            min = Math.min(min,root.val - pre);
        }
        pre = root.val;
        getMinimumDifference(root.right);
        return min;
    }
}

No.6 Lowest Common Ancestor of a Binary Tree

题目：https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/submissions/

解题思路：

令左子树找到为left，右子树找到为right，中间符合为mid，mid+left+right >= 2 即可找到了lca

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode res;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        boolean flag = helper(root,p,q);
        return flag ? res : null;
    }
    private boolean helper(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return false;
        int mid = (root == p || root == q) ? 1 : 0;
        int left = helper(root.left,p,q) ? 1 : 0;
        int right = helper(root.right,p,q) ? 1 : 0;
        if (mid + left + right >= 2) {
            res = root;
        } 
        return (mid + left + right) > 0;
    }
}

No.7 Convert Sorted List to Binary Search Tree

题目链接：https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

题目解析：

为了让bst平衡，需要找到list的中点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return new TreeNode(head.val);
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = new ListNode(0);
        pre.next = slow;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            pre = slow;
            slow = slow.next;
        }
        TreeNode root = new TreeNode(slow.val);
        pre.next = null;
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(slow.next);
        return root;
    }
}

No.8  Increasing Order Search Tree

题目链接：https://leetcode.com/problems/increasing-order-search-tree/

题目解析：

solution1:linkedlist 存储 再转为TreeNode，

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    LinkedList<TreeNode> res = new LinkedList<TreeNode>();
    public TreeNode increasingBST(TreeNode root) {
        inorder(root);
        TreeNode head = new TreeNode(0);
        TreeNode cur = head;
        for (TreeNode node : res) {
            cur.right = new TreeNode(node.val);
            cur = cur.right;
        }
        return head.right;
    }
    private void inorder(TreeNode root) {
        if (root == null) return;
        if (root.left != null) inorder(root.left);
        res.add(root);
        if (root.right != null) inorder(root.right);
    }
}

solution2:TreeNode inorder遍历的同时注意指针关系，将遍历的指针.left 赋值为null，不然会有环出现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    TreeNode res = new TreeNode(0);
    TreeNode head = res;
    public TreeNode increasingBST(TreeNode root) {
        inorder(root);
        return res.right;
    }
    private void inorder(TreeNode root) {
        if (root == null) return;
        if (root.left != null) inorder(root.left);
        root.left = null;
        head.right = root;
        head = root;
        if (root.right != null) inorder(root.right);
    }
}

No.9 Two Sum IV - Input is a BST

题目：https://leetcode.com/problems/two-sum-iv-input-is-a-bst/

解题思路：

Solution1: inorder取出list则是升序，前后两个指针ij去找sum = k

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> list = new ArrayList<Integer>();
    public boolean findTarget(TreeNode root, int k) {
        inorder(root);
        for (int i = 0, j = list.size() - 1; i < j; ) {
            int res = list.get(i) + list.get(j);
            if (res == k) return true;
            if (res < k) i++;
            else j--;
        }
        return false;
    }
    private void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        list.add(root.val);
        inorder(root.right);
    }
}

Solution2: 利用hashset存储已经遍历过的值，每次用k-root.val的值去hashset里寻找值

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> list = new ArrayList<Integer>();
    public boolean findTarget(TreeNode root, int k) {
        HashSet<Integer> set = new HashSet<Integer>();
        return dfs(root,k,set);
    }
    private boolean dfs(TreeNode root, int k, HashSet<Integer> set) {
        if (root == null) return false;
        if (set.contains(k - root.val)) return true;
        set.add(root.val);
        return dfs(root.left,k,set) || dfs(root.right,k,set);
    }
}

No.10 Delete Node in a BST

题目链接：https://leetcode.com/problems/delete-node-in-a-bst/

解题思路：

先找到key，然后在删除时有以下几种情况

  • left right 为空，return null
  • left 为空 right 不为空，return right
    • left 不为空 right 为空，return left
      • left 不为空 right 不为空，找到 right 的最小值，将right的最小值赋值给root。val进行替换，随后删除right中的最小值
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    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 minNode = findMin(root.right);
            root.val = minNode.val;
            root.right = deleteNode(root.right,minNode.val);
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
        } else {
            root.left = deleteNode(root.left, key);
        }
        return root;
    }
    private TreeNode findMin(TreeNode root) {
        while (root.left != null) {
            root = root.left;
        }
        return root;
    }

}

字典树Trie

字典树用来判断字符串是否存在或者是否具有某种字符串前缀的问题

No.1 Implement Trie (Prefix Tree)

题目链接：https://leetcode.com/problems/implement-trie-prefix-tree/

解题思路：

class TrieNode {
    TrieNode[] list;
    boolean is_val;
    public TrieNode() {
        list = new TrieNode[26];
    }
}

class Trie {
    TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (cur.list[c - 'a'] == null) {
                cur.list[c - 'a'] = new TrieNode();
            } 
            cur = cur.list[c - 'a'];
        }
        cur.is_val = true;
    }
    
    public boolean search(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (cur.list[c - 'a'] == null) {
                return false;
            }
            cur = cur.list[c - 'a'];
        }
        return cur.is_val;
    }
    
    public boolean startsWith(String prefix) {
        TrieNode cur = root;
        for (int i = 0;i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            if (cur.list[c - 'a'] == null) {
                return false;
            }
            cur = cur.list[c - 'a'];
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

全部评论

相关推荐

11-04 11:15
游卡_游戏客户端开发(准入职员工)
点赞 评论 收藏
分享
头像
11-05 21:12
小天才_电子工程师(准入职员工)
点赞 评论 收藏
分享
09-12 14:26
已编辑
门头沟学院 Java
点赞 评论 收藏
分享
10-16 15:48
算法工程师
点赞 评论 收藏
分享
11-01 02:10
门头沟学院 Java
26秋招京东零售后端一面
一面&nbsp;1、自我介绍&nbsp;2、在实习或项目中详细讲一下最有挑战性的点&nbsp;3、你对自己未来的职业发展有什么样的倾向或想法？&nbsp;4、平时使用的&nbsp;JDK&nbsp;版本有哪些？不同版本有哪些区别&nbsp;5、讲一下你已知的所有&nbsp;GC&nbsp;算法，总结一下&nbsp;GC&nbsp;算法在不同&nbsp;JDK&nbsp;版本中的迭代方向是什么？&nbsp;6、不同版本的&nbsp;GC&nbsp;有什么主要特点？（例如&nbsp;CMS,&nbsp;G1,&nbsp;ZGC）&nbsp;7、Java&nbsp;中有哪些锁机制？&nbsp;8、"ReentrantLock"&nbsp;内部是靠什么核心结构来保护共享资源的？&nbsp;9、创建一个新线程怎么做，它的主要成本（资源消耗）有哪些？&nbsp;10、如何使用&nbsp;Spring&nbsp;控制事务？&nbsp;11、主方法有&nbsp;"@Transactional"...
点赞 评论 收藏
分享
评论
1
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 同bg的你秋招战况如何？ #
171561次浏览 999人参与
# 扒一扒那些奇葩实习经历 #
125284次浏览 1094人参与
# 京东开奖 #
458189次浏览 2539人参与
# 你实习是赚钱了还是亏钱了？ #
26496次浏览 224人参与
# 去哪儿求职进展汇总 #
145401次浏览 994人参与
# 用一句话形容你的团队氛围 #
16579次浏览 172人参与
# 360集团校招 #
18657次浏览 146人参与
# 毕业论文进行时 #
5015次浏览 74人参与
# 面对逼签的应对技巧 #
5310次浏览 29人参与
# 我来点评面试官 #
14086次浏览 103人参与
# 牛友的国庆旅行碎片 #
20713次浏览 125人参与
# 今年秋招是回暖还是遇冷 #
27788次浏览 173人参与
# 秋招开始捡漏了吗 #
72664次浏览 513人参与
# 找工作八股要背到什么程度？ #
15721次浏览 232人参与
# 三一集团提前批进度交流 #
41262次浏览 229人参与
# 社会教会你的第一课 #
109920次浏览 859人参与
# 工作后，谈恋爱还和学生时代一样吗？ #
40875次浏览 377人参与
# 上班后，才发现大学__白学了 #
13969次浏览 100人参与
# 你找工作是从容有余 or 匆忙滚爬？ #
10012次浏览 85人参与
# 阿里云工作体验 #
33185次浏览 108人参与
# 你的领导最像哪种动物，为什么? #
25563次浏览 136人参与
# 职场破冰，你们都聊什么？ #
30695次浏览 154人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务