Pratique de l'arbre binaire itération récursive de l'arbre binaire 257, 100, 222, 101, 226, 437, 563, 617, 572, 543, | 687

257. Tous les chemins de l'arbre binaire

Compte tenu d'un arbre binaire,Renvoie tous les chemins du noeud racine au noeud foliaire.

Description: Un noeud foliaire est un noeud sans noeud Enfant.

Exemple:

Entrée:

1
/
2 3

5

Produits: [“1->2->5”, “1->3”]

Explication: Le chemin entre tous les noeuds racine et feuille est: 1->2->5, 1->3
Explication du problème：
1）dfs
2）bfs La file d'attente détermine si le noeud foliaire est,Pas la queue.,Est ajouté au chemin jusqu'à ce que la file d'attente soit vide
solution：

class Solution {
    
    public List<String> binaryTreePaths(TreeNode root) {
    
        List<String> res=new ArrayList<>();
        if(root==null) return res;
        dfs(root,"",res);
        return res;
    }
    public void dfs(TreeNode root,String cur,List<String> res){
    
        if(root==null) return;
        cur+=root.val;
        if(root.left==null&&root.right==null) res.add(cur);
        else {
    
         dfs(root.left,cur+"->",res);
         dfs(root.right,cur+"->",res);
    }
    }
}

543. Diamètre de l'arbre binaire

Un arbre binaire donné,Vous devez calculer son diamètre et sa longueur.La longueur diamétrale d'un arbre binaire est la plus grande des deux longueurs de chemin nodal.Ce chemin peut ou non passer par le noeud racine.
Explication du problème：Récursion Traverser chaque noeud, Calculer le chemin le plus long （ Longueur latérale du sous - arbre gauche + Longueur latérale du sous - arbre droit ）,Mettre à jour les variables globalesmax.

class Solution {
    
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
    
        if (root == null) {
    
            return 0;
        }
        dfs(root);
        return max;
    }
    
    private int dfs(TreeNode root) {
    
        if (root.left == null && root.right == null) {
    
            return 0;
        }
        int leftSize = root.left == null? 0: dfs(root.left) + 1;
        int rightSize = root.right == null? 0: dfs(root.right) + 1;
        max = Math.max(max, leftSize + rightSize);
        return Math.max(leftSize, rightSize);
    }  
}

563. Pente de l'arbre binaire

Compte tenu d'un arbre binaire, Calculer la pente de l'arbre entier .
La pente d'un noeud d'arbre est définie comme , Valeur absolue de la différence entre la somme des noeuds du sous - arbre gauche du noeud et la somme des noeuds du sous - arbre droit . La pente du noeud vide est 0.
La pente de l'arbre entier est la somme des pentes de tous ses noeuds ,
Explication du problème：
1）Récursion
La pente de l'arbre entier est la somme des pentes de tous ses noeuds , Calculer Récursivement la pente de chaque noeud . C'est - à - dire la pente du sous - arbre gauche de chaque noeud et Avec Pente du sous - arbre droit et ;
La pente du sous - arbre et = Valeur du noeud racine du sous - arbre + La pente du sous - arbre gauche et + La somme des pentes du sous - arbre droit ;Continuer la décomposition, Jusqu'à ce qu'il se décompose en arbre vide , La pente de l'arbre vide est 0, Pour la sortie récursive .
sloution：
1）java Math.abs() Méthode de calcul de la valeur absolue

class Solution {
    
    public int findTilt(TreeNode root) {
    
    if(root==null) return 0;
    return Math.abs(s(root.left)-s(root.right)) +findTilt(root.left)+findTilt(root.right);
    }
    private int s(TreeNode root){
    
    if(root == null) return 0;    
    return root.val + s(root.right) +s(root.left);
    }
}

617. Fusionner les arbres binaires

Compte tenu des deux arbres binaires,Imaginez quand vous écrasez l'un d'eux sur l'autre,Certains noeuds des deux arbres binaires se chevauchent.
Vous devez les fusionner en un nouvel arbre binaire.La règle de fusion est que si deux noeuds se chevauchent,Ajoutez leurs valeurs comme nouvelles valeurs après la fusion des noeuds,Sinon, non. NULL Le noeud de sera directement utilisé comme noeud du nouvel arbre binaire.

Explication du problème：
Récursion：Application de la traversée pré - ordonnée
sloution：

class Solution {
    
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    
        if (t1 == null && t2 == null) {
    
            return null;}
    TreeNode root = new TreeNode((t1 == null ? 0 : t1.val) + (t2 == null ? 0 : t2.val));
    root.left = mergeTrees(t1 == null ? null : t1.left, t2 == null ? null : t2.left);
    root.right = mergeTrees(t1 == null ? null : t1.right, t2 == null ? null : t2.right);
    return root;
}
}

226. /27.Retourner l'arbre binaire

Explication du problème：
1）Récursion
2）Itération：File d'attente. Tant que cette file d'attente n'est pas vide , Il sort toujours du noeud de file d'attente , Ensuite, échangez les noeuds enfants gauche et droit de ce noeud , Ensuite, mettez les noeuds enfants dans la file d'attente ,Retour au noeud racine
sloution:
1）Récursion c++

class Solution {
    
public:
    TreeNode* invertTree(TreeNode* root) {
    
        if (root == NULL) {
    
            return NULL;
        }
        swap(root->left, root->right);
        invertTree(root->left);
       invertTree(root->right);
        return root;
    }
};

2）Itération Officiellementjava

public TreeNode invertTree(TreeNode root) {
    
    if (root == null) return null;
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);
    while (!queue.isEmpty()) {
    
        TreeNode current = queue.poll();
        TreeNode temp = current.left;
        current.left = current.right;
        current.right = temp;
        if (current.left != null) queue.add(current.left);
        if (current.right != null) queue.add(current.right);
    }
    return root;
}

101. Arbre binaire symétrique

Compte tenu d'un arbre binaire,Vérifiez qu'il est miroir symétrique.
Explication du problème：
1）Récursion ComplexitéO(n)
2）Itération：En file d'attente, Une méthode courante pour réécrire Récursivement en itérations .
Chaque foispop Comparaison des deux noeuds , Insérez les sous - noeuds gauche et droit des deux autres noeuds dans la file d'attente dans l'ordre inverse .
sloution：
1）Récursion java

class Solution {
    
    public boolean isSymmetric(TreeNode root) {
    
        return cmp(root,root);
    }
    private boolean cmp(TreeNode t1,TreeNode t2){
    
        if(t1==null && t2==null) return true;
        if(t1==null || t2==null) return false;
        if(t1.val!=t2.val) return false;
        return cmp(t1.left,t2.right) && cmp(t1.right,t2.left);
    }
}

2）Itération c++Explication officielle：

class Solution {
    
public:
    bool check(TreeNode *u, TreeNode *v) {
    
        queue <TreeNode*> q;
        q.push(u); q.push(v);
        while (!q.empty()) {
    
            u = q.front(); q.pop();
            v = q.front(); q.pop();
            if (!u && !v) continue;
            if ((!u || !v) || (u->val != v->val)) return false;

            q.push(u->left); 
            q.push(v->right);

            q.push(u->right); 
            q.push(v->left);
        }
        return true;
    }

    bool isSymmetric(TreeNode* root) {
    
        return check(root, root);
    }
};

222. Nombre de noeuds dans un arbre binaire complet

Donne un arbre binaire complet,Trouvez le nombre de noeuds dans l'arbre.
Un arbre binaire complet est défini comme suit：Dans un arbre binaire complet,Sauf que le noeud le plus bas n'est peut - être pas plein,Le nombre maximum de noeuds par couche restante est atteint,Et les noeuds de la couche la plus basse sont concentrés à plusieurs endroits à l'extrême gauche de cette couche.Si le bas est h Couche,Cette couche contient 1~ 2h Noeuds.
C'est - à - dire:： Un arbre vide ou ses noeuds foliaires ne sortent que des deux dernières couches ,Si la dernière couche est insatisfaite, le noeud foliaire n'est qu'à l'extrême gauche.
Explication du problème：
1）javaRécursion -> Les propriétés des arbres binaires complets ne sont pas utilisées

class Solution {
    
    public int countNodes(TreeNode root) {
    
        if(root==null) return 0;
        return countNodes(root.left)+countNodes(root.right)+1;
    }
}

2） Définir la hauteur du sous - arbre gauche left, Hauteur du sous - arbre droit right.
Si égal,Le Sous - arbre gauche est plein d'arbres binaires, Le nombre total de noeuds dans le Sous - arbre gauche est 2^left -1,Plus cecirootNoeud,Oui.2^left ,Puis les statistiques récursives du sous - arbre droit.
Sinon, le Sous - arbre droit est plein d'arbres binaires ,Noeud de sous - arbre droit+rootNoeud,Total2^right.Ensuite, faites une recherche récursive sur le Sous - arbre gauche.
Note:：Opérations de bits Déplacer à gauche équivaut à *2

class Solution {
    
    public int countNodes(TreeNode root) {
    
        if (root == null) {
    
            return 0;
        }
        int left = countLevel(root.left);
        int right = countLevel(root.right);
        if (left == right) {
    
            return countNodes(root.right) + (1 << left);
        } else {
    
            return countNodes(root.left) + (1 << right);
        }
    }
// Calculer le nombre de couches 
    private int countLevel(TreeNode root) {
    
        int level = 0;
        while (root != null) {
    
            level++;
            root = root.left;
        }
        return level;
    }
}

100. Même arbre

Compte tenu des deux arbres binaires,Écrivez une fonction pour vérifier qu'elles sont identiques.Si les deux arbres sont structurellement identiques,Et le noeud a la même valeur,Ils sont considérés comme identiques.

Explication du problème：
Récursion Trois types de jugement
1、Tout est vide、Même chose.
2、Un vide.、Un non vide,C'est différent.
3、 Ni vide, mais valC'est différent.

class Solution {
    
    public boolean isSameTree(TreeNode p, TreeNode q) {
    
        if(p==null&&q==null)  return true;
        if(p!=null && q!=null && p.val==q.val){
    
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
        }
        else return false;
    }
}

572. Un enfant d'un autre arbre

Compte tenu de deux arbres binaires non vides s Et t,Inspection s Y a - t - il et t Sous - arbre avec la même structure et la même valeur de noeud.s Un sous - arbre de s Un noeud de ce noeud et tous les descendants de ce noeud .s Peut également être considéré comme un sous - arbre en soi.
Explication du problème：
Double récursion
Soit les deux arbres sont égaux
Soit cet arbre est un enfant de l'arbre de gauche
Soit cet arbre est un enfant de l'arbre de droite

sloution：

class Solution {
    
    public boolean isSubtree(TreeNode s, TreeNode t) {
    
    if (t==null) return true;
    if (s==null) return false;
    return isSubtree(s.right,t) || isSubtree(s.left,t) || isSameTree(s,t);
    }

    public boolean isSameTree(TreeNode s, TreeNode t){
    
    if(s==null&t==null) return true;
    if(s!=null && t!=null && s.val==t.val){
     
    return isSameTree(s.left,t.left) && isSameTree(s.right,t.right);
        }
        else return false;
    }
}

404.L'arbre de recherche binairekGrand noeud

Un arbre donnéArbre de recherche binaire,Trouvez le numéro.kGrands noeuds.

Explication du problème：
1） La séquence qui en résulte est ordonnée （Incrémental）
2） Par la question No. k Grand est l'ordre moyen traversant l'ordre inverse ：Racine droite gauche NokPetit：Gauche, droite

sloution：
1） Pour la traversée de l'ordre moyen ArrayListEnregistrement

class Solution {
    
    public int kthLargest(TreeNode root, int k) {
    
        List<Integer> list = new ArrayList<>();
        helper(root, list);
        return list.get(list.size() - k);
    }
    
    private void helper(TreeNode root, List<Integer> list) {
    
        if (root == null) return;
        if (root.left != null) helper(root.left, list);
        list.add(root.val);
        if (root.right != null) helper(root.right, list);
    }
}

2）Optimisation récursive：Passer à lak Arrêtez quand vous êtes grand

class Solution {
    
    private int ans = 0, cnt = 0;
    public int kthLargest(TreeNode root, int k) {
    
        dfs(root, k);
        return ans;
    }
    private void dfs(TreeNode root, int k) {
    
        if(root == null) return ;
        dfs(root.right, k);
        if(++cnt == k) {
    
            ans = root.val;
        }
        dfs(root.left, k);
    }
}

3）Itération：Utiliser la pile