笔试面试高频考点二叉树、树和二叉树（1）——数据结构

• 树是一种 非线性 数据结构，它的根朝下，叶子朝上，因为很像倒过来的树，所以叫树。

1）节点 / 树的度

• 节点度：一个节点包含子树的数量
• 树度：所有节点中最大的度是树度

2）叶子 / 终端节点

• 度为 0 的节点

3）双亲 / 父节点

• 如果一个节点包含子节点，则该节点是子节点的父母 / 父节点

4）子 / 孩子节点

• 包含子树根节点的节点是节点的子节点

5）根节点

• 没有双亲节点的节点是根节点

6）高度 / 深度

• 从上到下，树木的最大层次

1)父母/孩子/孩子的父母/孩子的兄弟 表示法

• 兄弟表示法最常用

• 每个节点的度不超过2棵树
• 树为空也是二叉树

1）满二叉树

• 树的高度是k，树的节点数为 2^k - 1

2)完全二叉树

• 从左到右编号满二叉树，满二叉树的每个节点的编号都可以与满二叉树一起编号 一对应
• 满二叉树是一种特殊的完全二叉树

1)非空二叉树 i 层节点最多 2^(i - 1)

2)树的节点最多 2^i - 1

3)叶节点数n0、度为2的非叶节点数为n2，则满足 n0 = n2 1

4）完全二叉树的节点个数为n，二叉树的高度为 log(n 1) 向上取整

5)节点数为n的完全二叉树，从上到下从左到右 从0开始 给每个节点序列号，一个节点序列号i，所以父节点是（i - 1）/ 2；父节点

序号为i，子节点为 2i 1 和 2i 2 (子节点存在时)

6)树是完全二叉树，当节点数为偶数时，度为1的节点数为 1；为奇数，度为1 节点个数为0

• 一般使用二叉树 孩子表示法 储存主要用于平衡树木

static class TreeNode{ 
                 public char val;         public TreeNode left;         public TreeNode right;          public TreeNode(char val) { 
                     this.val = val;         }     } 

1）NLR：前序遍历 2）LNR：中序遍历 3）LRN：后序遍历

1）思路：

• 进入 左树 右树，根据 具体遍历 确定打印 或者 其它操作(如集合) 时机

（2）解法：

• 遍历法

 public void preOderTraveral(Node root){ 
                 if(root == null){ 
                     return;         }          System.out.print(root.val " "); preOderTraveral(root.left); preOderTraveral(root.right); } public void inOderTraveral(Node root){ 
          if(root == null){ 
          return; } inOderTraveral(root.left); System.out.print(root.val+" "); inOderTraveral(root.right); } public void postOderTraveral(Node root){ 
          if(root == null){ 
          return; } postOderTraveral(root.left); postOderTraveral(root.right); System.out.print(root.val+" "); } 

• 子问题

 public List<Integer> preorderTraversal(TreeNode root) { 
        
    //先创建list，如果root为空直接返回空list
    List<Integer> ret = new LinkedList<>();
    
    if(root == null) return ret;

    List<Integer> left = preorderTraversal(root.left);
    List<Integer> right = preorderTraversal(root.right);

    ret.addAll(left);
    ret.addAll(right);

    return ret;
}

//2中
public List<Integer> inorderTraversal(TreeNode root) { 
        
    List<Integer> ret = new LinkedList<>();

    if(root == null) return ret;

    List<Integer> leftTree = inorderTraversal(root.left);
    ret.addAll(leftTree);

    List<Integer> rightTree = inorderTraversal(root.right);
    ret.addAll(rightTree);

    return ret;

}

//3后
public List<Integer> postorderTraversal(TreeNode root) { 
        
    List<Integer> ret = new LinkedList<>();

    if(root == null) return ret;

    List<Integer> left = postorderTraversal(root.left);
    ret.addAll(left);

    List<Integer> right = postorderTraversal(root.right);
    ret.addAll(right);

    return ret;
}

1）解法：

• 遍历法

public static int size = 0;
    public int size1(TreeNode root){ 
        
        if(root == null) return size;

        size++;

        size1(root.left);
        size1(root.right);

        return size;
    }

• 子问题

public int size2(TreeNode root){ 
        
        int size = 0;
        if(root == null) return size;

        int leftSize = size2(root.left);
        int rightSize = size2(root.right);

        return leftSize + rightSize + 1;
    }

1）解法：

• 遍历法

public static int leafSize = 0;
    public int getLeafNodeCount1(TreeNode root){ 
        
        if(root == null) return leafSize;

        if(root.left == null && root.right == null) leafSize++;

        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);

        return leafSize;
    }

• 子问题

public int getLeadNodCount2(TreeNode root){ 
        
    int leafSize = 0;

    if (root == null) return leafSize;

    if(root.left == null && root.right == null) leafSize++;

    int leftLeafSize = getLeadNodCount2(root.left);
    int rightLeafSize = getLeadNodCount2(root.right);

    return leafSize + leftLeafSize + rightLeafSize;
}

1）解法：

• 遍历法

public int getLevelNodeCount(TreeNode root, int k){ 
        
    if(root == null) return 0;

    if(k == 1) return 1;

    return getLevelNodeCount(root.left, k - 1) + getLevelNodeCount(root.right, k - 1);
}

1)思路：

• 使用子问题思路，递归中止条件就是root.val == val / null

• 左右树分别递归，递归完成后使用ret接收，同时进行判空 返回

2）代码：

public TreeNode find(TreeNode root, int val){ 
        
    if(root == null) return  null;

    if(root.val == val) return root;

    TreeNode ret = find(root.left, val);
    if(ret != null) return ret;


    ret = find(root.right, val);
    if(ret != null) return ret;

    return null;
}

1）思路：

• 使用子问题思路递归，中止条件为root == null

• 左右树分别进行递归，记录左右树的高度。递归都完成后，返回两树高度较大值+1

• tip：如果使用三目运算符进行嵌套可能会导致递归次数太多，而超时错误

2）时间复杂度：

• O(n)，每个节点都要进行求树的高度

3）解法：

• 子问题

public int getHeight(TreeNode root){ 
        
    if(root == null) return 0;
    
    //提前保存左右树的高度，如果直接在在三目运算符中嵌套，可能会因为超时而报错
    int leftHeight = getHeight(root.left);
    int rightHegiht = getHeight(root.right);

    return leftHeight > rightHegiht ? leftHeight + 1 : rightHegiht + 1;
    
    //return (getHeight(root.left) > getHeight(root.right)) ? getHeight(root.left) + 1 : getHeight(root.right) + 1;
}

1）返回类型为void

（1）思路：

• 根节点判空，创建队列，传入root

• 保存出队根节点，将该 根节点的非空子节点入队，依次循环 直到队列为空（一次循环出队一个节点）

（2）解法

public void leverOrder(TreeNode root){ 
        
    if(root == null) return;

    Queue<TreeNode> queue= new LinkedList<>();
    queue.offer(root);

    while(!queue.isEmpty()){ 
        
        TreeNode tmp = queue.poll();
        System.out.print(tmp.val + " ");

        if(tmp.left != null) queue.offer(tmp.left);

        if(tmp.right != null) queue.offer(tmp.right);
    }

    System.out.println();
}

2）返回类型为 List<List> （1）思路：

• 总：出上层，入下层，尾插上层

  • 创建 List<List> ret保存层序遍历的结果
  • 创建Queue queue储存本层的节点，来源于上次外循环的入队
  • 创建List list保存本层的节点，内循环结束尾插到ret中

• 一次外循环表示处理完一层的元素，包括各自保存本层和下层的非空元素

• 一次内循环出队size个节点，出队节点 传入临时list，同时入队 出队节点 的非空子节点，一次循环结束将list尾插到ret。

  • szie = queue.size()，是queue保存的本层节点个数
  • list 在内循环中初始化

• tip:先初始化 list，当root == null 时返回ret

（2）解法：

public List<List<Integer>> levelOrder(TreeNode root) { 
        
    List<List<Integer>> ret = new LinkedList<>();

    if(root == null ) return ret;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while(!queue.isEmpty()){ 
        
        List<Integer> list = new LinkedList<>();
        int size = queue.size();

        while(size != 0){ 
        
            TreeNode node = queue.poll();
            list.add(node.val);

            if(node.left != null){ 
        
                queue.offer(node.left);
            }

            if(node.right != null){ 
        
                queue.offer(node.right);
            }

            size--;
        }

        ret.add(list);

    }
    return ret;
}

1） 前序遍历

（1）思路

• 总：栈保存节点，根为空出栈找到右节点，循环至栈空

• 初始化栈 stack，创建 cur = root 遍历节点

• 外循环 限制条件为 cur 非空 或者 栈非空

• 内循环 限制条件cur 非空，先入栈cur打印cur，再cur左移。跳出内循环，左节点打印完毕，出栈根节点top，cur = top.right进入右节点 ，完成一次外循环。

  • 进入右节要将在栈中的根节点出掉，才能到下一次右节点为空的时候 找到要遍历的另一棵树的根节点（打印路径中的下一个右节点）

（2）解法：

public void preOrderTravelNor(Node root){ 
        
    if(root == null) return;
    Stack<Node> stack = new Stack<>();
    Node cur = root;

    while(!stack.empty() || cur != null){ 
        
        while(cur != null){ 
        
            stack.push(cur);
            System.out.print(cur.val + " ");
            cur = cur.left;
        }

        Node top = stack.pop();
        cur = top.right;
    }

}

2）中序遍历

（1）思路：

• 大体和前序遍历类似，因为中序遍历是 左 根 右，所以等cur到达 要打印的树 的最左边元素后，出栈根节点时再打印

（2）解法：

public void inOrderTravelNor(Node root){ 
        
    if(root == null) return;
    Stack<Node> stack = new Stack<>();
    Node cur = root;

    while(cur != null || !stack.empty()){ 
        
        while(cur != null){ 
        
            stack.push(cur);
            cur = cur.left;
        }

        Node top = stack.pop();
        System.out.print(top.val + " ");
        cur = cur.right;
    }
}

3）后序遍历

（1）思路：

• 总：将第一个要打印的元素看作一个主体节点，该主体节点可能是父节点cur的左节点或者右节点，如果是左节点直出栈打印，如果是右节点则要加上判断 cur.right == pre打印过的节点，避免陷入死循环。
• a 内循环到最左边的节点，判断该节点的右节点。右节点分空和非空两种情况，cur.right == null空直接将该节点出栈打印，同时将cur 赋值为空下次循环直接回到根节点；非空cur = cur.right 将其视为新的根节点继续循环
• b 如果是非空右节点，循环至要打印的根节点（即该节点的子字节点都为空）进行出栈打印，打印完成后，我们要退回该节点的根节点将其打印
• 我们的目标是只打印该根节点（出栈操作），不打印已经打印过的右节点
• 仅仅依靠原有（a）中的cur.right == null判空代码，又会重新进入根节点的右节点，陷入打印的死循环
• 所以我们 加上cur.right == pre(上次打过的的节点)，直接出栈中元素，不进入已打印过的右节点

public void postOrderTravelNor(Node root){ 
        
    if(root == null) return;
    Stack<Node> stack = new Stack<>();
    Node cur = root;
    Node pre = null;

    while(cur != null || !stack.empty()){ 
        
        while(cur != null){ 
        
            stack.push(cur);
            cur = cur.left;
        }

        //取出堆顶元素，不出队，因为可能右节点非空
        cur = stack.peek();

        //cur.right == pre 操作防止回到根节点后再进入右节点
        if(cur.right == null || cur.right == pre){ 
        
            Node popNode = stack.pop();
            System.out.print(popNode.val + " ");
            pre = cur;

            //cur = null 不会重复进入左节点，直接回到根节点
            cur = null;
        }else{ 
        
            cur = cur.right;
        }
    }
}