圈圈小站

quanquan's blog

0%

树专题

发表于 分类于

剑指offer 树专题。

1.重建二叉树

递归法

  • 前序遍历的首元素 为 树的根节点 node 的值。
  • 在中序遍历中搜索根节点 node 的索引 ，可将 中序遍历 划分为 [ 左子树 | 根节点 | 右子树 ] 。
  • 根据中序遍历中的左 / 右子树的节点数量，可将 前序遍历 划分为 [ 根节点 | 左子树 | 右子树 ] 。
根节点索引 中序遍历左边界 中序遍历右边界
左子树 root + 1 left i - 1
右子树 i - left + root + 1 i + 1 right 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    unordered_map<int, int> dic;
    TreeNode* treenode(int root, int left, int right, vector<int>& preorder){
        if (left>right) return NULL;
        TreeNode* node = new TreeNode(preorder[root]);
        int i = dic[preorder[root]];
        node->left = treenode(root+1,left,i-1,preorder);
        node->right = treenode(root+i-left+1,i+1,right,preorder);
        return node;

    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for (int i=0; i<inorder.size(); i++){
            dic[inorder[i]] = i;
        }
        return treenode(0,0,inorder.size()-1,preorder);
    }
};

2.二叉树的镜像

时间复杂度 O(N)： 其中 N 为二叉树的节点数量，建立二叉树镜像需要遍历树的所有节点，占用 O(N) 时间。
空间复杂度 O(N) ： 最差情况下（当二叉树退化为链表），递归时系统需使用 O(N) 大小的栈空间。

1
2
3
4
5
6
7
TreeNode* mirrorTree(TreeNode* root) {
        if (root == NULL) return root;
        TreeNode* temp = root->left;
        root->left = mirrorTree(root->right);
        root->right = mirrorTree(temp);
        return root;
    }

3.对称的二叉树

【法一】递归

  • 对称二叉树定义： 对于树中 任意两个对称节点 L 和 R ，一定有：
    • $L.val = R.val$：即此两对称节点值相等。
    • $L.left.val = R.right.val$ ：即 L 的 左子节点 和 R 的 右子节点 对称；
    • $L.right.val = R.left.val$ ：即 L 的 右子节点 和 R 的 左子节点 对称。

Picture1.png

1
2
3
4
5
6
7
8
9
10
11
bool judge(TreeNode* left, TreeNode* right){
       if (!left&&!right) return true;
       if (!left||!right||left->val!=right->val){
           return false;
       }
       return judge(left->left,right->right) && judge(left->right,right->left);
   }
   bool isSymmetric(TreeNode* root) {
       if (root==NULL) return true;
       return judge(root->left,root->right);
   }

【法二】队列

4.二叉树的深度

1
2
3
4
5
int maxDepth(TreeNode* root) {
    if (root == NULL)
        return 0;
    return max(maxDepth(root->left),maxDepth(root->right))+1;
}

5.二叉搜索树

二叉搜索树的中序遍历为递增序列

求二叉搜索树的第k大节点

中序遍历的倒序：右、根、左

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int ans;
    int kthLargest(TreeNode* root, int k) {
        if (root==NULL) return 0;
        dfs(root,k);
        return ans;
    }
    void dfs(TreeNode* root, int &k){
        if (root==NULL) return;
        dfs(root->right,k);
        k--;
        if (k==0){
            ans = root->val;
            return;
        }
        dfs(root->left,k);
    }
};

6.判断是不是平衡二叉树

后序遍历+剪枝

  • 时间复杂度 O(N)： N 为树的节点数；最差情况下，需要递归遍历树的所有节点。
  • 空间复杂度 O(N)： 最差情况下（树退化为链表时），系统递归需要使用 O(N) 的栈空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
int depth(TreeNode* root){
    if (root==NULL) return 0;
    int l = depth(root->left);
    if (l==-1) return -1;
    int r = depth(root->right);
    if (r==-1) return -1;
    if (abs(l-r)<2) return max(l,r)+1;
    return -1;
}
bool isBalanced(TreeNode* root) {
    if (depth(root)==-1) return false;
    else return true;
}

6.求最近公共祖先

递归查找 若当前节点的左子结点中含有p|q 且右子节点中也含有p|q 则返回当前节点；否则返回左/右子节点。

1
2
3
4
5
6
7
8
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root==NULL||root==p||root==q) return root;
        TreeNode* left = lowestCommonAncestor(root->left,p,q);
        TreeNode* right = lowestCommonAncestor(root->right,p,q);
        if (left==NULL) return right;
        if (right==NULL) return left;
        return root;
    }