没有递归的给定二叉树节点的打印祖先


难度级别 中等
经常问 ol石 亚马逊 风筝
树遍历

给定一棵二叉树和一个特定的节点或密钥。 给定的印刷祖先 二叉树 没有递归的节点。

没有递归的给定二叉树节点的打印祖先

使用案列

输入:

键= 7

没有递归的给定二叉树节点的打印祖先

输出: 3 1

输入:

键= 4

没有递归的给定二叉树节点的打印祖先

输出: 2 1

给定二叉树节点祖先的算法

  1. 创建一个类Node,该类包含一个用于容纳数据的整数变量和左右两个Node类型的对象。 在其中创建参数化构造函数,该参数构造函数接受一个整数值作为参数,并将其存储在类节点的整数变量中。
  2. 之后,创建函数以打印给定键的祖先,该键接受树的根节点,并将键作为参数。
  3. 检查根是否等于null,返回。 否则创建类型为node的堆栈数据结构。
  4. 开始遍历给定的二进制文件 .
  5. 当root不等于null且root的数据不等于给定的键时,将root推入堆栈并更新root作为root的左边。
  6. 如果根不等于null并且根的数据等于给定的键,则中断循环。
  7. 否则,如果堆栈顶部节点的权利等于null,则更新堆栈顶部节点的根,然后弹出堆栈顶部。 当堆栈不为空且堆栈顶部节点的右边等于根节点时,请更新堆栈顶部节点的根节点,然后弹出堆栈顶部。 .
  8. 如果堆栈为空,则将根更新为null,否则将根更新为堆栈顶部节点的右侧。
  9. 当堆栈不为空时,在堆栈顶部打印节点的数据,然后弹出堆栈顶部。

给定二叉树节点祖先的C ++程序

#include <bits/stdc++.h> 
using namespace std; 
  
struct Node{ 
    int data; 
    struct Node *left, *right; 
}; 
  
struct Node* newNode(int data){ 
    struct Node* node = (struct Node*) malloc(sizeof(struct Node)); 
    node->data = data; 
    node->left = node->right = NULL; 
    return node; 
} 
  
void printAncestors(struct Node *root, int key){ 
    if(root == NULL){ 
        return; 
    }
  
    stack<struct Node* > st; 
  
    while(1){ 
        while(root && root->data != key){ 
            st.push(root);  
            root = root->left;
        } 
  
        if(root && root->data == key){ 
            break; 
        }
  
        if(st.top()->right == NULL){ 
            root = st.top(); 
            st.pop(); 
  
            while(!st.empty() && st.top()->right == root){ 
               root = st.top(); 
               st.pop(); 
            } 
        } 
  
        root = st.empty()? NULL: st.top()->right; 
    } 
  
    while(!st.empty()){ 
        cout<<st.top()->data<<" "; 
        st.pop(); 
    } 
} 
  
int main(){ 
    
    struct Node* root = newNode(1); 
    root->left = newNode(2); 
    root->right = newNode(3); 
    root->left->left = newNode(4); 
    root->left->right = newNode(5); 
    root->right->left = newNode(6); 
    root->right->right = newNode(7); 
    
    int key = 7;
    
    printAncestors(root, key); 
  
    return 0; 
}
3 1

给定二叉树节点祖先的Java程序

import java.util.Stack; 
  
class findAncestors{ 
    
    static class Node{ 
        int data; 
        Node left,right; 
          
        Node(int data){ 
            this.data = data; 
        } 
    } 
      
    static void printAncestors(Node root,int key){ 
        if(root == null){ 
            return; 
        }
          
        Stack<Node> st = new Stack<>(); 
          
        while(true){ 
              
            while(root != null && root.data != key){ 
                st.push(root);   
                root = root.left;
            } 
              
            if(root != null && root.data == key){ 
                break; 
            }
              
            if(st.peek().right == null){ 
                root =st.peek(); 
                st.pop(); 
                  
                while( st.empty() == false && st.peek().right == root){ 
                    root = st.peek(); 
                    st.pop(); 
                } 
            } 
              
            root = st.empty() ? null : st.peek().right; 
        } 
          
        while(!st.empty()){ 
            System.out.print(st.peek().data+" "); 
            st.pop(); 
        } 
    } 
      
    public static void main(String[] args){ 
         
        Node root = new Node(1); 
        root.left = new Node(2); 
        root.right = new Node(3); 
        root.left.left = new Node(4); 
        root.left.right = new Node(5); 
        root.right.left = new Node(6); 
        root.right.right = new Node(7); 
        
        int key = 7;
        
        printAncestors(root, key); 
    } 
  
}
3 1

复杂度分析

时间复杂度: O(n)其中n是插入的节点数。

空间复杂度: O(n),因为我们将空间用于n个节点。

參考資料