遍历二叉树

  1. public static class TreeNode{
  3.         static List qianxu = new ArrayList<>();
  4.         static List zhongxu = new ArrayList<>();
  5.         static List houxu = new ArrayList<>();
  6.         public static void main(String[] args) {
  9.             /**
  10.              *            0
  11.              *       1         2
  12.              *    3     4    8   9
  13.              * 5   6 10   7
  14.              */
  16.             Tree tree = new Tree(0);
  17.             Tree a = new Tree(1);
  18.             Tree b = new Tree(2);
  19.             Tree c = new Tree(3);
  20.             Tree d = new Tree(4);
  21.             Tree e = new Tree(5);
  22.             Tree f = new Tree(6);
  23.             Tree g = new Tree(7);
  24.             Tree h = new Tree(8);
  25.             Tree i = new Tree(9);
  26.             Tree j = new Tree(10);
  28.             tree.left = a;
  29.             tree.right = b;
  30.             a.left = c;
  31.             a.right = d;
  32.             c.left = e;
  33.             c.right = f;
  34.             d.right = g;
  35.             b.left = h;
  36.             b.right = i;
  37.             d.left = j;
  40.             List list = houxu(tree);
  41.             for(int q =0;q<list.size();q++){
  42.                 System.out.print(list.get(q)+" ");
  43.             }
  45.             //cengci(tree);
  48.         }
  51.         /**
  52.          * 前序遍历  中 左 右
  53.          * @param node
  54.          * @return
  55.          */
  56.         public static List qianxu(Tree node){
  57.             qianxu.add(node.val);
  58.             if(node.left != null){
  59.                 qianxu(node.left);
  60.             }
  61.             if(node.right != null){
  62.                 qianxu(node.right);
  63.             }
  65.             return qianxu;
  66.         }
  68.         /**
  69.          * 中序遍历 左 中 右
  70.          * @param node
  71.          * @return
  72.          */
  73.         public static List zhongxu(Tree node){
  74.             if(node.left != null){
  75.                 zhongxu(node.left);
  76.             }
  77.             zhongxu.add(node.val);
  78.             if(node.right != null){
  79.                 zhongxu(node.right);
  80.             }
  81.             return zhongxu;
  82.         }
  85.         /**
  86.          * 后序遍历 左 右 中
  87.          * @param node
  88.          * @return
  89.          */
  90.         public static List houxu(Tree node){
  91.             if(node.left != null){
  92.                 houxu(node.left);
  93.             }
  94.             if(node.right != null){
  95.                 houxu(node.right);
  96.             }
  97.             houxu.add(node.val);
  98.             return houxu;
  99.         }
  100.     }

层级遍历

  1. /**
  2.          * 层次遍历
  3.          * @param node
  4.          */
  5.         public static void cengci(Tree node){
  6.             ArrayDeque<Tree> queue = new ArrayDeque<>(20);
  7.             //首先将根节点加入栈中
  8.             queue.add(node);
  9.             //遍历二叉树
  10.             while (!queue.isEmpty()) {
  11.                 //pop（）函数和poll（）函数都是从首位置取元素并删除；
  12.                 //区别在于，pop遇到null会报异常。poll遇到null会返回null。
  13.                 Tree tempNode = queue.poll();
  14.                 System.out.print(tempNode.val + " ");
  16.                 if(tempNode.left != null){
  17.                     queue.add(tempNode.left);
  18.                 }
  19.                 if(tempNode.right != null){
  20.                     queue.add(tempNode.right);
  21.                 }
  22.             }
  23.         }

二叉搜索树的最近公共祖先

  1. // 235. 二叉搜索树的最近公共祖先
  2. public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  3.         if(p.val == root.val){
  4.             return p;
  5.         }
  6.         if(q.val == root.val){
  7.             return q;
  8.         }
  10.         if(p.val > root.val && q.val > root.val){
  11.             return lowestCommonAncestor(root.right,p,q);
  12.         }else if(p.val < root.val && q.val < root.val){
  13.             return lowestCommonAncestor(root.left,p,q);
  14.         }else{
  15.             return root;
  16.         }
  17.     }

数组转二叉树

思路：涉及二叉树时，一般使用递归

//108. 将有序数组转换为二叉搜索树
    public TreeNode sortedArrayToBST(int[] nums) {
        return buildTree(nums,0,nums.length-1);
    }

    private TreeNode buildTree(int[] nums,int l,int r){
        if(l > r){
            return null;
        }
        int n = l + (r-l)/2;
        TreeNode root = new TreeNode(nums[n]);
        root.left = buildTree(nums,l,n-1);
        root.right = buildTree(nums,n+1,r);
        return root;
    }