澳门新葡8455手机版-澳门新葡8455最新网站

您的位置:澳门新葡8455手机版 > 新闻资讯 > 一律的左右子树也都以二叉树.,假设某二叉树的

一律的左右子树也都以二叉树.,假设某二叉树的

2019-10-09 08:08

主题素材须求:输入二叉树的根节点,判定该树是不是是平衡二叉树。要是某二叉树的大肆节点的左右子树深度之差不超过1,则该树是平衡二叉树。

节点定义

使用单向链表的花样,只保留当前节点的子节点和权值,不保留父节点.

typedef struct Node{
    int value;//权值,根据实际情况而定,这里用数字
    Node *lChild;//左儿子节点
    Node *rChild;//右儿子节点
}BNode;

运作结果

参照小说

二叉树-你一定要懂!

思路2:假设用后序遍历,那么访谈某一个节点时一度访谈了它的左右子树。同临时间,在走访节点时记下下它的深度,并由左右子树的吃水推出老爹节点的吃水,那样我们就能够透过遍历二遍降成整棵树的平衡性推断。对于某一个子树,供给提交它的平衡性的决断,还要给出它的吃水,此处小编将平衡性的剖断作为再次回到值,深度通过长度为1的数组传递出去,见boolean isBalanced2Core(TreeNode<Integer> node,int[] depth)。

后序遍历

递归版:
先遍历左子树,然后遍历右子树,再遍历根节点

void postorderTraversal(BNode *rootNode) {
    if(rootNode != NULL) {
        postorderTraversal(rootNode->lChild);
        postorderTraversal(rootNode->rChild);
        printf("%d ", rootNode->value);
    }
}

非递归版:
后序遍历的非递归版和先序遍历、中序遍历区别,这里笔者用五个栈来达成,三个栈来保存遍历节点并持续的张开弹出,贰个栈来保存节点的遍历顺序,最终遍历第一个栈.

void postorderTraversalNonrecursive(BNode *rootNode) {
    stack<BNode *>s1;
    stack<BNode *>s2;
    if (rootNode == NULL ) {
        return ;
    }
    s1.push(rootNode);
    while(!s1.empty()) {
        BNode *tempNode = s1.top();
        s1.pop();
        s2.push(tempNode);
        if (tempNode->lChild) {
            s1.push(tempNode->lChild);
        }
        if (tempNode->rChild) {
            s1.push(tempNode->rChild);
        }
    }
    while(!s2.empty()) {
        printf("%d ", s2.top()->value);
        s2.pop();
    }
}
package chapter6;import structure.TreeNode;/** * Created with IntelliJ IDEA * Author: ryder * Date : 2017/8/17 * Time : 10:03 * Description:平衡二叉树 **/public class P273_isBalanced { //借助于深度,判断是否是平衡二叉树,由于是从根到叶逐点判断,需要多次遍历树 public static boolean isBalanced(TreeNode<Integer> node){ if(node==null) return true; int left = treeDepth(node.left); int right = treeDepth(node.right); int diff = left - right; if(diff<-1||diff>1) return false; return isBalanced(node.left)&&isBalanced(node.right); } public static int treeDepth(TreeNode<Integer> root){ if(root==null) return 0; int left = treeDepth(root.left); int right = treeDepth(root.right); return left>right?:; } //用后序遍历,并记录每个节点的深度,从而可以通过一次遍历完成整棵树的判断 public static boolean isBalanced2(TreeNode<Integer> node){ if(node==null) return true; return isBalanced2Core(node,new int[]{0}); } public static boolean isBalanced2Core(TreeNode<Integer> node,int[] depth){ if(node==null){ depth[0] = 0; return true; } int[] left = new int[]{0}; int[] right = new int[]{0}; if(isBalanced2Core(node.left,left)&&isBalanced2Core(node.right,right)){ int diff = left[0]-right[0]; if(diff<=1&&diff>=-1){ depth[0] = 1+(left[0]>right[0]?left[0]:right[0]); return true; } else return false; } return false; } public static void main(String[] args){ TreeNode<Integer> root = new TreeNode<>; root.left = new TreeNode<>; root.left.left = new TreeNode<>; root.left.right = new TreeNode<>; root.left.right.left = new TreeNode<>; root.right = new TreeNode<>; root.right.right = new TreeNode<>; System.out.println(isBalanced; System.out.println(isBalanced2; }}

二叉树的遍历

二叉树的遍历分为三种:

  • 前序遍历
    先遍历当前节点(根节点),然后遍历左儿子节点,再遍历右外孙子节点
  • 中序遍历
    先遍历左外孙子节点,然后遍历当前节点(根节点),再遍历右孙子节点
  • 后序遍历
    先遍历左外孙子节点,然后遍历右外孙子节点,再遍历当前节点(根节点)

咱俩创制二叉树的时候平时用的是递归的主意,不过二叉树的遍历能够有递归和非递归二种格局.上面会分别交付二叉树遍历递归和非递归的笔触和代码.

PS:建议看懂思路后再看代码达成,然后手动模拟一下,效果更佳.

本连串导航:剑指offerjava完结导航帖

S型打字与印刷二叉树

此处作者动用的是队列 + 栈来达成的,队列存款和储蓄当前遍历的节点的行列,栈中存款和储蓄下一层遍历的节点顺序,使用一个level 来判定遍历方向

void STraversal(BNode *rootNode) {
    queue<BNode *>q;
    stack<BNode *>s;
    int level = 1;//根节点为第一层
    q.push(rootNode);
    while(!q.empty()){
        BNode *temp;
        while(!q.empty()){
            temp = q.front();
            printf("%d ", temp->value);
            if (level % 2) {//下一层要从左到右遍历
                if (temp->rChild != NULL) {
                    s.push(temp->rChild);
                }
                if (temp->lChild != NULL) {
                    s.push(temp->lChild);
                }
            } else {//下一层要从右到左遍历
                if (temp->lChild != NULL) {
                    s.push(temp->lChild);
                }
                if (temp->rChild != NULL) {
                    s.push(temp->rChild);
                }
            }
            q.pop();
        }
        while(!s.empty()){
            temp = s.top();
            //将下一层节点的按照遍历顺序加入队列中
            q.push(temp);
            s.pop();
        }
        level++;
    }
}
truetrue

中序遍历

递归版:
先遍历左子树,然后遍历根节点,再遍历右子树

void inorderTraversal(BNode *rootNode) {
    if(rootNode != NULL) {
        inorderTraversal(rootNode->lChild);
        printf("%d ", rootNode->value);
        inorderTraversal(rootNode->rChild);
    }
}

非递归版:
和先序遍历同样的怀恋,因为要先拜见左子树,然后再拜会根节点(当前节点),那么在栈弹出的时候进行输出即为所求.

对于任一结点node:

  • 若其左孩子不为空,则将node入栈并将node的左孩子置为眼下的node,然后对眼下结点P再开展一样的拍卖;
  • 若其左孩子为空,则取栈顶元素并打开出栈操作,访谈该栈顶结点,然后将日前的node置为栈顶结点的右孩子;
  • 以致于node为NULL并且栈为空则遍历停止
void inorderTraversalNonrecursive(BNode *rootNode) {
    stack<BNode *>s;
    if (rootNode == NULL ) {
        return ;
    }
    BNode *tempNode = rootNode;
    while(!s.empty() || tempNode != NULL) {
        while(tempNode != NULL) {
            s.push(tempNode);
            tempNode = tempNode->lChild;
        }
        if (!s.empty()) {
            tempNode = s.top();
            s.pop();
            printf("%d ", tempNode->value);
            tempNode = tempNode->rChild;
        }
    }
}

面试题55.2:平衡二叉树

判定完全二叉树

一起二叉树即叶节点只好出现在最下层和次下层,并且最上边一层的结点都聚焦在该层最侧边包车型大巴几何职责的二叉树

就此可得出判别的七个原则:

  • 假若有个别节点的右子树不为空,则它的左子树必得不为空
  • 借使有些节点的右子树为空,则排在它背后的节点必需未有子女节点

就此大家能够安装一个标记位flag,当子树满意完全二叉树时,设置flag=YES。当flag=YES而节点又破坏了完全二叉树的规格,那么它就不是截然二叉树。

bool checkIsCompleteBTree(BNode *rootNode) {
    if (rootNode == NULL) {
        return true;
    }
    queue<BNode *>q;
    q.push(rootNode);
    bool flag = false;
    while(!q.empty()){
        BNode *tempNode = q.front();
        q.pop();
        if (tempNode->lChild == NULL && tempNode->rChild != NULL) {
            return false;
        }
        if (tempNode->lChild == NULL && tempNode->rChild == NULL) {
            flag = true;
        }
        if (flag == true && tempNode->lChild != NULL && tempNode->rChild != NULL) {
            return false;
        }
        if (tempNode->lChild != NULL) {
            q.push(tempNode->lChild);
        }
        if (tempNode->rChild != NULL) {
            q.push(tempNode->rChild);
        }
    }
    return flag;
}

解题思路:思路1:依赖平衡二叉树的定义化解。借助于上一题二叉树的纵深,从根节点初步逐点判断树的左右子树的深度差值是或不是满足供给。由于此解法是从根到叶的判别,每三遍获得节点有要求从脚下节点遍历到叶节点,由此供给屡次遍历。

求多个节点间的门径

独家将多少个节点到根节点的路子求出,然后对根节点到多个节点的近来集体祖先节点的不二秘籍进行去重就可以.

void findPathBetweenTwoNode(BNode *rootNode, BNode *node1, BNode *node2, vector<BNode *> &path){
    vector<BNode *>path1;
    findPathFromNodetoRoot(rootNode, node1, path1);
    vector<BNode *>path2;
    findPathFromNodetoRoot(rootNode, node2, path2);

    vector<BNode *>::iterator it1 = path1.begin();
    vector<BNode *>::iterator it2 = path2.begin();
    BNode *LCANode;
    int cnt = 0;
    //去重
    while(it1 != path1.end() && it2 != path2.end()) {
        if (*it1 == *it2) {
            LCANode = *it1;
            cnt++;
        }
        it1++;
        it2++;
    }
    for(int i = cnt - 1; i < path1.size(); i++) {
        path.push_back(path1[i]);
    }
    reverse(path.begin(), path.end());
    for(int i = cnt; i < path2.size(); i++) {
        path.push_back(path2[i]);
    }
}

求树的一层某个许节点

根节点某层的节点数 = 左子树中某层的节点数 + 右子树中某层的节点数

设置一个层数变量 level,在递归进程中,通过 level 的减少模拟下跌的经过,当level = 1的时候证实抵达了我们要找的那一层,那么重临当前节点数,也等于1.

int findNumOfNodeOnLevel(BNode *rootNode, int level) {
    if (level == 0 || rootNode == NULL) {
        return 0;
    }
    if(level == 1){
        return 1;
    }
    return findNumOfNodeOnLevel(rootNode->lChild, level - 1) + findNumOfNodeOnLevel(rootNode->rChild, level - 1);
}

看清平衡二叉树

又被称之为AVL树(有别于AVL算法),且富有以下性质:它是一 棵空树或它的左右多个子树的万丈差的相对化值不超越1,並且左右七个子树都是一棵平衡二叉树.
递归检查各样节点的左右子树的万丈之差是或不是符合必要,重临就能够.

bool checkLR(BNode *rootNode, int &height) {
    if (rootNode == NULL) {
        return true;
    }
    if (rootNode->value > rootNode->rChild->value || rootNode->value < rootNode->lChild->value) {
        return false;
    }
    bool lAns = checkLR(rootNode->lChild, height);
    int lHeight = height;
    bool rAns = checkLR(rootNode->rChild, height);
    int rHeight = height;
    height = max(lHeight, rHeight) + 1;
    if (lAns == true && rAns == true && abs(lHeight - rHeight) <= 1) {
        return true;
    } else {
        return false;
    }
}
bool checkBalanceBTree(BNode *rootNode) {
    int height = 0;
    return checkLR(rootNode, height);
}

求树的直径(树上多个节点间的最大距离)

此处有两种方案:

方案一:

直白遍历每一种点,模拟当前点为三个节点路线的契机时的最大距离,那么也便是时下节点的左子树深度

  • 右子树深度,然后取最大值

光阴复杂度: O(n^2)

int findDiameterOfTree1(BNode *rootNode) {
    if(rootNode == NULL) {
        return 0;
    }
    return max(max(findDiameterOfTree1(rootNode->lChild), findDiameterOfTree1(rootNode->rChild)), findDeepOfTree(rootNode->lChild) + findDeepOfTree(rootNode->rChild));
}

方案二:

在求子树深度的时候就将最远距离求出

int findMaxDeep(BNode *rootNode, int &ans) {
    if (rootNode == NULL) {
        return 0;
    }
    int leftDeep = findMaxDeep(rootNode->lChild, ans);
    int rightDeep = findMaxDeep(rootNode->rChild, ans);
    ans = max(ans, leftDeep + rightDeep);
    return max(leftDeep, rightDeep) + 1;
}
int findDiameterOfTree2(BNode *rootNode) {
    int ans = 0;
    findMaxDeep(rootNode, ans);
    return ans;
}

扭曲二叉树

这里穿插贰个小逸事,二零一五 年 6 月 10 日,Homebrew 的撰稿人 Max Howell 在 twitter 上刊载了如下一内容:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

粗粗意思正是:他在应聘谷歌(Google)的时候被面试官说:尽管有十分七的人在用你写的软件,可是你不会翻转二叉树,所以说大家不会援引你.
因为 马克斯 Howell 的影响力,所以这件职业一下子广为流传.

回去正题:翻转二叉树,便是二叉树的镜像,相当于将二叉树的左右子树对调,这里有三种方案;

递归版:

void swapTree(BNode *&root){
    BNode *tmp = root->lChild;
    root->lChild = root->rChild;
    root->rChild = tmp;
}
void turnBTree(BNode *rootNode) {
    if (rootNode == NULL) {
        return ;
    }
    turnBTree(rootNode->lChild);
    turnBTree(rootNode->rChild);
    swapTree(rootNode);
}

非递归版:

void invertBinaryTreeNonrecursive2(BNode *root) {
    if(root == NULL){
        return ;
    }
    stack<BNode *>s;
    s.push(root);
    while(!s.empty())
    {
        BNode *tmp = s.top();
        s.pop();
        swapTree(tmp);
        if(tmp->lChild){
            s.push(tmp->lChild);
        }
        if(tmp->rChild){
            s.push(tmp->rChild);
        }
    }
}

前言

本文代码落成为 C/C++,因为不是贰个完全的授课小说,只是私有思路,所以说思路讲授也可能有不足之处,有错误请提出.

什么样是二叉树?

引用自百度健全:
在Computer科学中,二叉树是各类节点最多有四个子树的树结构。经常子树被称作“左子树”(left subtree)和“右子树”(right subtree),同样的左右子树也都以二叉树.

分段遍历二叉树

即每便输出二叉树的一层,比方:

贯彻思路:广度优先遍历(BFS),使用队列来落到实处,每一趟遍历当前节点的左右幼子节点,并将其参加队列中,然后开展队列的弹出直到队列为空.

void levelTraversal(BNode *rootNode) {
    queue<BNode *>q;
    q.push(rootNode);
    while(!q.empty()) {
        BNode *tempNode = q.front();
        q.pop();
        printf("%d ", tempNode->value);
        if (tempNode->lChild) {
            q.push(tempNode->lChild);
        }
        if (tempNode->rChild) {
            q.push(tempNode->rChild);
        }
    }
}

二叉树深度

一棵空树的纵深为0,独有根节点的数的深度为1,所以说三个数的吃水 = max(左子树的吃水,右子树的深浅) + 1(当前节点),使用递归来求.

int findDeepOfTree(BNode *rootNode){
    if(rootNode == NULL){
        return 0;
    }
    return max(findDeepOfTree(rootNode->lChild), findDeepOfTree(rootNode->rChild)) + 1;
}

求七个节点到根节点的路线

概念贰个从某节点到根节点的栈,这里运用 vector 来落到实处,具体步骤:

  • 将眼下节点压入栈中
  • 探究当前节点左子树是不是含有要物色节点(递归实行)
    • 固然有,栈中寄放的正是路径
    • 万一未有,再找找右子树是不是含有要物色节点
      • 若果有,栈中存放的正是路径
      • 假诺都没有,弹出当前节点,在遍历栈中的上多个节点
bool findPathFromNodetoRoot(BNode *rootNode, BNode *node, vector<BNode *> &path) {
    if (rootNode == NULL || node == NULL) {
        return false;
    }
    path.push_back(rootNode);
    if (rootNode == node) {
        return true;
    }
    bool isFind = findPathFromNodetoRoot(rootNode->lChild, node, path);
    if (isFind == false) {
        isFind = findPathFromNodetoRoot(rootNode->rChild, node, path);
    }
    if (isFind == false) {
        path.pop_back();
    }
    return isFind;
}

树的肥瘦

树的上升的幅度就是节点最多的一层的节点数,依照前边分层遍历二叉树的规律,每回从队列中抽取一层的节点,将其子节点参与队列,然后查看节点数,即队列的大小.

int findWidthOfTree(BNode *rootNode){
    queue<BNode *>q;
    q.push(rootNode);
    int ansWidth = 1;
    while(!q.empty()) {
        for(int i = 0; i < q.size(); i++) {
            BNode *tempNode = q.front();
            q.pop();
            if (tempNode->lChild) {
                q.push(tempNode->lChild);
            }
            if (tempNode->rChild) {
                q.push(tempNode->rChild);
            }
        }
        ansWidth = max(ansWidth, (int)q.size());
    }
    return ansWidth;
}

前序遍历

递归版:
先遍历根节点,然后遍历左子树,再遍历右子树
那些出色的递归观念,驾驭二叉树的属性和递归观念就能够得出.

void preorderTraversal(BNode *rootNode) {
    if(rootNode != NULL) {
        printf("%d ", rootNode->value);
        preorderTraversal(rootNode->lChild);
        preorderTraversal(rootNode->rChild);
    }
}

非递归版:

动用栈来完成,因为 C++ 中有现有的库,所以说就不手动模拟栈了,当遍历到三个节点的时候,先将此节点输出,然后径直遍历其左孙子,依次循环,直到遇见叶子节点,然后伊始弹,也等于递归进程中的回溯。

对于任一结点node:

  • 做客结点node,并将结点node入栈;
  • 认清结点node的左孩子是还是不是为空
  • 若为空,则取栈顶结点并打开出栈操作,并将栈顶结点的右孩子置为当前的结点node,循环至1
  • 若不为空,则将node的左孩子置为当前的结点node;
  • 直至node为NULL并且栈为空,则遍历结束。
void preorderTraversalNonrecursive(BNode *rootNode) {
    stack<BNode *>s;
    if (rootNode == NULL ) {
        return ;
    }
    BNode *tempNode = rootNode;
    while(!s.empty() || tempNode != NULL) {
        while(tempNode != NULL) {
            printf("%d ", tempNode->value);
            s.push(tempNode);
            tempNode = tempNode->lChild;
        }
        if (!s.empty()) {
            tempNode = s.top();
            s.pop();
            tempNode = tempNode->rChild;
        }
    }
}

求叶子节点数

叶子节点,即不含子节点的节点,当二个节点的左右幼子皆为空的时候,此节点为叶子节点,所以能够得出:树的叶子节点数 = 左子树的叶子节点数 + 右子树的卡牌节点数.

int findNumOfLeafNode(BNode *rootNode){
    if(rootNode == NULL) {
        return 0;
    }
    if(rootNode->lChild == NULL && rootNode->rChild == NULL) {
        return 1;
    }
    return findNumOfLeafNode(rootNode->lChild) + findNumOfLeafNode(rootNode->rChild);
}

求多少个节点的方今公共祖先

万一当前遍历到了三个根节点,那么检查我们要查究的三个节点在时下节点的哪些子树中,会有二种情景:

  • 都在左子树
  • 都在右子树
  • 四个在左子树,贰个在右子树

情景一和意况二的时候大家需求回到节点所在子树的遍历结果,意况三的时候证实大家早就找到了近年公共祖先(不明了的最棒手动模拟一下)。

BNode * findCommonNodeOfTwoNode(BNode *rootNode, BNode *node1, BNode *node2) {
    if (rootNode == NULL || node1 == NULL || node2 == NULL) {
        return NULL;
    }
    if (node1 == rootNode || node2 == rootNode) {
        return rootNode;
    }
    BNode *leftLCANode = findCommonNodeOfTwoNode(rootNode->lChild, node1, node2);//检查左子树
    BNode *rightLCANode = findCommonNodeOfTwoNode(rootNode->rChild, node1, node2);//检查右子树
    if (leftLCANode != NULL && rightLCANode != NULL) {//一个在左一个在右,找到目标
        return rootNode;
    }
    if (leftLCANode == NULL) {//全在右子树
        return rightLCANode;
    } else {//全在左子树
        return leftLCANode;
    }
}

再有一种方案正是将七个节点到根节点的路子都求出,然后开始对照,要是碰到第二个一样的节点即为所求,那么些留给读者本身完成吧.

本文由澳门新葡8455手机版发布于新闻资讯,转载请注明出处:一律的左右子树也都以二叉树.,假设某二叉树的

关键词: