一：对称二叉树

1. 递归

每次访问左右两个节点，不相同则为false

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return recursion(root->left, root->right);
    }
    bool recursion(TreeNode* left, TreeNode* right)
    {
        if (left == nullptr && right == nullptr) return true;       // 都为空
        if (left == nullptr || right == nullptr) return false;      // 其中一个为空
        return left->val == right->val && recursion(left->left, right->right) && recursion(left->right, right->left);   // 左节点的左节点与右节点的右节点，左节点的右节点与右节点的左节点
    }
};
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return recursion(root.left, root.right);
    }
    public boolean recursion(TreeNode left, TreeNode right)
    {
        if (left == null && right == null) return true;      
        if (left == null || right == null) return false;     
        return left.val == right.val && recursion(left.left, right.right) && recursion(left.right, right.left);   
    }
}
1
2
3
4
5
6
7
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        return self._recursion(root.left, root.right)
    def _recursion(self, left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:
        if left == None and right == None: return True      
        if (left == None or right == None): return False     
        return left.val == right.val and self._recursion(left.left, right.right) and self._recursion(left.right, right.left)

image-20251003132839039

2. 迭代

使用队列管理左右节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return iteration(root, root);
    }
    bool iteration(TreeNode* left, TreeNode* right)
    {
        queue<TreeNode*> treeQueue;
        treeQueue.push(left);
        treeQueue.push(right);
        while (!treeQueue.empty())
        {
            left = treeQueue.front();       // 先进先出
            treeQueue.pop();
            right = treeQueue.front();
            treeQueue.pop();
            if (left == nullptr && right == nullptr) continue;
            if (left == nullptr || right == nullptr || left->val != right->val) return false;
            treeQueue.push(left->left);
            treeQueue.push(right->right);
            treeQueue.push(left->right);
            treeQueue.push(right->left);
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return iteration(root, root);
    }
    public boolean iteration(TreeNode left, TreeNode right)
    {
        Queue<TreeNode> treeQueue = new LinkedList<>();
        treeQueue.offer(left);
        treeQueue.offer(right);
        while (!treeQueue.isEmpty())
        {
            left = treeQueue.poll();       // 先进先出
            right = treeQueue.poll();
            if (left == null && right == null) continue;
            if (left == null || right == null || left.val != right.val) return false;
            treeQueue.offer(left.left);
            treeQueue.offer(right.right);
            treeQueue.offer(left.right);
            treeQueue.offer(right.left);
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        return self._iteration(root, root)

    def _iteration(self, left, right) -> bool:
        treeQueue = []
        treeQueue.append(left)
        treeQueue.append(right)
        while (treeQueue):
            left = treeQueue.pop()      
            right = treeQueue.pop()
            if (left == None and right == None): continue
            if (left == None or right == None or left.val != right.val): return False
            treeQueue.append(left.left)
            treeQueue.append(right.right)
            treeQueue.append(left.right)
            treeQueue.append(right.left)
        return True

image-20251003132849925

二：二叉树的直径

image-20251003135943406

1. 深度优先

长度为节点数减1，通过递归可获得左右子树的深度，左右子树的深度+1则为经过的节点数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int nodeNum = 1;    // 初始节点为1，也可设为0表示长度
        recursion(nodeNum, root);
        return  nodeNum - 1;    // 返回长度
    }
    int recursion(int& nodeNum, TreeNode* node)
    {
        if (node == nullptr) return 0;
        int leftNum = recursion(nodeNum, node->left);
        int rightNum = recursion(nodeNum, node->right);
        nodeNum = max(nodeNum, leftNum + rightNum + 1);     // 拿到最大节点
        return max(leftNum, rightNum) + 1;      // 拿到深度
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int nodeNum = 0; // 初始长度为0
    public int diameterOfBinaryTree(TreeNode root) {
        recursion(root);
        return  nodeNum;    // 返回长度
    }
    public int recursion(TreeNode node)
    {
        if (node == null) return 0;
        int leftNum = recursion(node.left);
        int rightNum = recursion(node.right);
        nodeNum = Math.max(nodeNum, leftNum + rightNum);     // 拿到最大长度
        return Math.max(leftNum, rightNum) + 1;      // 拿到深度
    }
}
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.nodeNum = 0
        self._recursion(root)
        return  self.nodeNum    
    def _recursion(self, node) -> int:
        if (node == None): return 0
        leftNum = self._recursion(node.left)
        rightNum = self._recursion(node.right)
        self.nodeNum = max(self.nodeNum, leftNum + rightNum)     
        return max(leftNum, rightNum) + 1

image-20251003140032553

三：将有序数组转换为二叉搜索树

image-20251003143256105

1. 左边中序遍历

给定升序数组，对于二叉搜索树则是中序遍历，可将数组的中间数据或偏左作为根节点，左右两段分别为左右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return recursion(nums, 0, nums.size() - 1);
    }
    TreeNode* recursion(vector<int>& nums, int left, int right)
    {
        if (left > right) return nullptr;
        int mid = (left + right) / 2;       // 中间偏左或正中
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = recursion(nums, left, mid - 1);
        root->right = recursion(nums, mid + 1, right);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return recursion(nums, 0, nums.length - 1);		// 使用length
    }
    TreeNode recursion(int[] nums, int left, int right)
    {
        if (left > right) return null;
        int mid = (left + right) / 2;       // 中间偏左或正中
        TreeNode root = new TreeNode(nums[mid]);
        root.left = recursion(nums, left, mid - 1);
        root.right = recursion(nums, mid + 1, right);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        return self._recursion(nums, 0, len(nums) - 1)

    def _recursion(self, nums, left, right) -> Optional[TreeNode]:
        if (left > right): return None
        mid = (left + right) // 2       # 这里用//而非/
        root = TreeNode(nums[mid])
        root.left = self._recursion(nums, left, mid - 1)
        root.right = self._recursion(nums, mid + 1, right)
        return root

image-20251003143525085

2. 中间中序遍历

这里是用中间位置或偏右作为中间结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return recursion(nums, 0, nums.size() - 1);
    }
    TreeNode* recursion(vector<int>& nums, int left, int right)
    {
        if (left > right) return nullptr;
        int mid = (left + right + 1) / 2;       // 这里加1
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = recursion(nums, left, mid - 1);
        root->right = recursion(nums, mid + 1, right);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return recursion(nums, 0, nums.length - 1);
    }
    TreeNode recursion(int[] nums, int left, int right)
    {
        if (left > right) return null;
        int mid = (left + right + 1) / 2;      
        TreeNode root = new TreeNode(nums[mid]);
        root.left = recursion(nums, left, mid - 1);
        root.right = recursion(nums, mid + 1, right);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        return self._recursion(nums, 0, len(nums) - 1)

    def _recursion(self, nums, left, right) -> Optional[TreeNode]:
        if (left > right): return None
        mid = (left + right + 1) // 2       # 这里用//而非/
        root = TreeNode(nums[mid])
        root.left = self._recursion(nums, left, mid - 1)
        root.right = self._recursion(nums, mid + 1, right)
        return root

image-20251003143535005

3. 右边中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return recursion(nums, 0, nums.size() - 1);
    }
    TreeNode* recursion(vector<int>& nums, int left, int right)
    {
        if (left > right) return nullptr;
        int mid = (left + right + rand() % 2) / 2;       // 随机，rand返回一个伪随机的整数
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = recursion(nums, left, mid - 1);
        root->right = recursion(nums, mid + 1, right);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return recursion(nums, 0, nums.length - 1);
    }
    TreeNode recursion(int[] nums, int left, int right)
    {
        if (left > right) return null;
        Random rand = new Random();         // 随机对象
        int mid = (left + right + rand.nextInt(2)) / 2;       // 返回这个范围(2)内的随机整数
        TreeNode root = new TreeNode(nums[mid]);
        root.left = recursion(nums, left, mid - 1);
        root.right = recursion(nums, mid + 1, right);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        return self._recursion(nums, 0, len(nums) - 1)

    def _recursion(self, nums, left, right) -> Optional[TreeNode]:
        if (left > right): return None
        mid = (left + right + randint(0, 1)) // 2       # 随机整数的范围，包括起点和终点
        root = TreeNode(nums[mid])
        root.left = self._recursion(nums, left, mid - 1)
        root.right = self._recursion(nums, mid + 1, right)
        return root

image-20251003143543517

四：搜索插入位置

image-20251003153015776

1. 二分

根据二分查找的思想，依次比较中间点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2; // 避免溢出的写法，也可使用java的方法
            if (nums[mid] == target) {
                return mid; 
            } else if (nums[mid] < target) {
                left = mid + 1; 
            } else {
                right = mid - 1; 
            }
        }
        // 循环结束后，left 指针就是目标应该插入的位置
        return left;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1, cur = right + 1;
        while (left <= right)
        {
            int mid = ((right - left) >> 1) + left;       // 防止int越界
            if (target <= nums[mid])
            {
                cur = mid;
                right = mid - 1;
            } else
            {
                left = mid + 1;
            }
        }
        return cur;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1 
        cur = right + 1
        while (left <= right):
            mid = ((right - left) // 2) + left      
            if (target <= nums[mid]):
                cur = mid
                right = mid - 1
            else:
                left = mid + 1
        return cur

image-20251003153038306

五：有效的括号

image-20251003155246511

1. 栈

先把左括号放入栈中，遇到右括号则弹出栈顶，判断是否相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 != 0) return false;
        unordered_map<char, char> unMap = {
            {')', '('},
            {'}', '{'}, 
            {']', '['}};        // 遇到右括号寻找左括号
        stack<char> chStk;
        for (auto ch : s)
        {
            if (unMap.count(ch))
            {
                if (chStk.empty()) return false;
                char top = chStk.top();
                chStk.pop();
                if (unMap[ch] != top) return false;
            } else
            {
                chStk.push(ch);
            }
        }
        return chStk.empty();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public boolean isValid(String s) {
        if (s.length() % 2 != 0) return false;
        Map<Character, Character> unMap = new HashMap<>();          // 使用Character而非char
        unMap.put('}', '{');
        unMap.put(']', '[');
        unMap.put(')', '(');
        Deque<Character> chStk = new LinkedList<>();
        for (int i = 0; i < s.length(); ++i)
        {
            char ch = s.charAt(i);
            if (unMap.containsKey(ch))
            {
                if (chStk.isEmpty()) return false;
                char top = chStk.peek();
                chStk.pop();
                if (unMap.get(ch) != top) return false;
            } else
            {
                chStk.push(ch);
            }
        }
        return chStk.isEmpty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def isValid(self, s: str) -> bool:
        if (len(s) % 2 != 0): return False
        unMap = {
            '}': '{',
            ']': '[',
            ')': '(',
        }      
        chStk =[]
        for ch in s:
            if (ch in unMap):
                if (not chStk): return False
                top = chStk[-1]     # 最后一个值
                chStk.pop()         # 弹出
                if (unMap[ch] != top): return False
            else:
                chStk.append(ch)
        return not chStk

image-20251003155322440