在线问答5

这个屌丝很懒，什么也没留下！

热门标签

树与二叉树

作者：在线问答5 | 2024-07-16 21:35:41

踩

树与二叉树

前言：

树这个结构想必在日常生活中很常见到，而现在要介绍的是一种独特的数据结构--二叉树。

1.树

（1）定义：

是一种非线性结构，有一个特殊的节点叫做根节点，树没有前驱节点；树是递归定义的；树形结构中子树不能有交集，否则就不是树形结构。

（2）树相关重要概念：（如上图）

节点的度：一个节点含有的子树的个数。eg：A的度为2，B的度为3。

树的度：一棵树中，所有节点的度中的最大值。 eg：树的度为3.

叶子节点/终端节点：节点的度为0的节点。eg：叶子节点：E，D，G，F

双亲节点/父节点：若有一个节点含有子节点，则称这个节点为该子节点的双亲节点/父节点。

孩子节点/子节点：一个节点含有的子树的根节点称为该节点的子节点。

根节点：一颗树中，没有双亲节点的节点。

节点的层次：从根节点开始，根为第一层，根的子节点为第二层，以此类推。

树的高度/深度：树中节点的最大层次。eg：树的深度/高度为3.

2.二叉树

（1）定义：

该树中每个节点的度都小于等于2；且子树有左右子树之分。下图都是二叉树。

（2）两种特殊的二叉树：

a.完全二叉树：如果一颗树的节点个数为n，深度为K，且树中每一个节点都是深度为K的满二叉树中编号从0~(n-1)的节点，则称为完全二叉树。

b.满二叉树：每层节点数都是最大值 => 如果一颗树的高度为n，且树节点的总数为 $2^n-1$ ，则称为满二叉树。

（3）二叉树的性质：

a.若根节点的层数为1，则一颗非空二叉树的第i层上的节点最多有 $2^{i-1}$ 个。

b.若规定只有根节点的二叉树的深度为1，则深度为K的二叉树节点总数最多为 $2^{k}-1$ 。

c.对任何一颗二叉树，如果叶子节点的个数为 $n_0{}$ ，节点的度为2的节点个数为 $n_2{}$ ，则 $n_2{}$ +1= $n_0{}$ 。

d.具有n个节点的完全二叉树，则该树的深度为 $\log_{2}\left ( n+1 \right )$ 向上取整。

e.对于具有n个节点的完全二叉树，如果按照从上到下，从左到右的顺序对所有节点，从0开始编号，对于第i个节点有：

如果i>0，则双亲节点/父节点： $\frac{i-1}{2}$ ；如果i=0，则没有双亲节点/父节点；

如果2i+1<n，则该节点有左孩子；否则没有左孩子。

如果2i+2<n，则该节点有右孩子；否则没有右孩子。

f.对于一颗完全二叉树来说，如果该树节点总数为偶数个，则节点的度为1的节点只有一个；若为奇数个，则没有节点的度为1的节点。

（4）二叉树的遍历及其代码实现：

在实现二叉树的遍历之前，首先需要创建一个类TreeNode（二叉树的节点，包含该节点的值，该节点的左孩子节点，该节点的右孩子节点），所以：


class TreeNode {
    public TreeNode left;//左孩子
    public TreeNode right;//右孩子
    public int val;
    public TreeNode(int val) {
        this.val = val;
    }
}

a.前序遍历：根节点 -> 左子树 -> 右子树

分析：

代码实现：


public void preorderTraversal(TreeNode root) {
    if(root == null) {
        return;
    }
    System.out.print(root.val + " ");
    preorderTraversal(root.left);
    preorderTraversal(root.right);
}

b.中序遍历：左子树 -> 根节点 -> 右子树

分析：

代码实现：


public void inorderTraversal(TreeNode root) {
    if(root == null) {
        return;
    }
    preorderTraversal(root.left);
    System.out.print(root.val + " ");
    preorderTraversal(root.right);
}

c.后序遍历：左子树 -> 右子树 -> 根节点

分析：

代码实现：


public void lastorderTraversal(TreeNode root) {
    if(root == null) {
        return;
    }
    preorderTraversal(root.left);
    preorderTraversal(root.right);
    System.out.print(root.val + " ");
}

（5）二叉树相关OJ题：

二叉树所有的题都会涉及到递归。所有OJ题的前提都是已经创建好了一颗树，并且知道根节点为root。

a.求树的高度。

题析：

题解：


public int getHeight(TreeNode root) {
    if(root == null) {
        return 0;
    }
    int leftHeight = getHeight(root.left);
    int rightHeight = getHeight(root.right);
    return Math.max(leftHeight,rightHeight) + 1;//这里也可以用条件运算符
}

b.求树中叶子节点的个数。

题析：

题解：


public int getLeafNodeCount(TreeNode root) {
    if(root == null) {
        return 0;
    }
    if(root.left == null && root.right == null) {
        return 1;
    }    
    return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
}

c.第i层有多少个节点。

题析：

题解：


public int getKLevelNodeCount(TreeNode root, int k) {
    if(root == null) {
        return 0;
    }
    if(k == 1) {
        return 1;
    }
    return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);
}

d.判断某个val值是否存在于树中。

题析：

题解：


public TreeNode getVal(TreeNode root, int val) {
    if(root == null) {
        return null;
    }
    if(root.val == val) {
        return root;
    }
    TreeNode leftTree = getVal(root.left,val);
    if(leftTree != null) {
        return leftTree;
    }
    TreeNode rightTree = getVal(root.right,val);
    if(rightTree != null) {
        return rightTree;
    }
    return null;
}

e.节点的总个数。

题析：

题解：


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

f.检查两棵树是否相同

题析：

题解：


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

g.另一棵树的子树

题析：

题解：


class Solution {
    //判断两棵树的结构是否相同
    private boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) {
            return true;
        }
        if(p == null && q != null || q == null && p != null) {
            return false;
        }
        if(p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
 
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null) {
            return false;
        }
        if(isSameTree(root,subRoot)) {
           return true; 
        }
        return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }
}

h.翻转二叉树

题析：

题解：

法一：该种方法没有利用返回值（先序遍历）。


class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return null;
        }
        if(root.left == null && root.right == null) {
            return root;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

法二：利用返回值（后序遍历）。


class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return null;
        }
        if(root.left == null && root.right == null) {
            return root;
        }
        TreeNode leftNode = invertTree(root.left);
        TreeNode rightNode = invertTree(root.right);
        root.left = rightNode;
        root.right = leftNode;
        return root;
    }
}

i.是否为平衡二叉树

题析：

题解：

法一：该方法的时间复杂度为 $O\left ( n^{2} \right )$


class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        if(Math.abs(leftHeight - rightHeight) > 1) {
            return false;
        }  
        return isBalanced(root.left) && isBalanced(root.right);
    }
    private int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftHigh = getHeight(root.left);
        int rightHigh = getHeight(root.right);
        return Math.max(leftHigh,rightHigh) + 1;
    }
}

法二：可以实现时间复杂度为 $O\left ( n\right )$ ，只需要去修改getHeight方法，在求高度的过程中去判断是否每一个节点的高度差 <= 1。

题解：


class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }
        return getHeight(root) >= 0;
    }
    private int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftHigh = getHeight(root.left);
        if(leftHigh == -1) {
            return -1;
        }
        int rightHigh = getHeight(root.right);
 
        if(rightHigh >= 0 && Math.abs(leftHigh - rightHigh) <= 1) {
            return Math.max(leftHigh,rightHigh) + 1;
        }
        return -1;
    }
}

j.二叉树的构建与遍历

题析：

题解：


import java.util.Scanner;
class TreeNode {
    public char val;
    public TreeNode left;
    public TreeNode right;
 
    public TreeNode(char val) {
        this.val = val;
    }
}
 
public class Main {
    private static int i;
    //注意static修饰的变量，每次调用这个方法的时候都是对同一个变量进行修改的。
    //所以第二次调用该方法的时候，i不为0.所以需要在while循环中将i置0/使用非静态方法
    private static TreeNode createTree(String str) {
        TreeNode root = null;
        if (str.charAt(i) != '#') {
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        }else {
            i++;
        }
        return root;
}
    //中序遍历
    private static void inOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            i = 0;
            TreeNode root = createTree(str);
            inOrder(root);
        }
    }
}

k.对称二叉树

题析：

题解：


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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/在线问答5/article/detail/836286