先、中、后序遍历

    1. const tree = {
    2.     val: 1,
    3.     left: {
    4.         val: 2,
    5.         left: {
    6.             val: 3,
    7.             left: null,
    8.             right: null,
    9.         },
    10.         right: {
    11.             val: 4,
    12.             left: null,
    13.             right: null,
    14.         }
    15.     },
    17.     right: {
    18.         val: 5,
    19.         left: {
    20.             val: 6,
    21.             left: null,
    22.             right: null,
    23.         },
    24.         right: {
    25.             val: 7,
    26.             left: null,
    27.             right: null,
    28.         }
    29.     }
    30. }
    32. // // 根，左，右
    33. // const preorder = (root) => {
    34. //     if(!root) {return }
    35. //     console.log(root.val);
    37. //     preorder(root.left);
    38. //     preorder(root.right);
    39. // }
    41. // preorder(tree);
    44. // 左，根, 右，
    45. // const inorder = (root) => {
    46. //     if(!root) {return }
    47. //     inorder(root.left);
    48. //     console.log(root.val);
    50. //     inorder(root.right);
    51. // }
    53. // inorder(tree);
    55. // 左， 右，根,
    56. const postorder = (root) => {
    57.     if(!root) {return }
    58.     postorder(root.left);
    59.     postorder(root.right);
    60.     console.log(root.val);
    62. }
    64. postorder(tree);
    66. // ========================================== 非递归
    68. // 前序 根，左，右
    69. // const preorder = (root) => {
    70. //     if(!root) {return }
    71. //     const stack = [root];
    73. //     while(stack.length) {
    74. //         const n = stack.pop();
    75. //         console.log(n.val);
    77. //         // 栈是先进后出，所以我们先把右节点push进去
    78. //         if(n.right) stack.push(n.right)
    79. //         if(n.left) stack.push(n.left)
    80. //     }
    81. // }
    83. // preorder(tree);
    85. // 中序左，根, 右，
    86. // const inorder = (root) => {
    87. //     if(!root) {return }
    89. //     const stack = [];
    90. //     let p = root;
    92. //     while(stack.length || p) {
    93. //         while(p) {
    94. //             stack.push(p);
    95. //             p = p.left
    96. //         }
    97. //         const n = stack.pop();
    98. //         console.log(n.val);
    100. //         p = n.right
    101. //     }
    103. // }
    105. // inorder(tree);
    107. // 后序 左， 右，根,
    108. const postorder = (root) => {
    109.     if(!root) {return }
    111.     const stack = [root];
    112.     const outPutStack = [];
    114.     while(stack.length) {
    115.         const n = stack.pop();
    116.         outPutStack.push(n)
    117.         // 栈是先进后出，所以我们先把右节点push进去
    118.         if(n.left) stack.push(n.left)
    119.         if(n.right) stack.push(n.right)
    120.     }
    122.     while(outPutStack.length) {
    123.         const n = outPutStack.pop();
    124.         console.log(n.val);
    125.     }
    127. }
    129. postorder(tree);